13182022-05-12 21:43:14nkdorka1212Testnevelés óracpp11Hibás válasz 28/50158ms38056 KiB
#include <bits/stdc++.h>

using namespace std;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

int n,k;
vector<int>befok;
vector<vector<int>>g;
vector<bool>vis;
vector<int>mo;
int db=0;
bool ketto=false;
int l,r;

int bfs()
{
    queue<int>q;
    for(int i=1;i<=n;i++)
    {
        if(befok[i]==0)
        {
            q.push(i);
        }
    }
    if(q.size()==0)
    {
        return -1;
    }else
    {
        if(q.size()>=2)
        {
            ketto=true;
            l=0,r=1;
        }
        while(!q.empty())
        {
            int v=q.front();
            q.pop();
            mo.push_back(v);
            for(int x:g[v])
            {
                befok[x]--;
                int db1=0;
                if(befok[x]==0 && !vis[x])
                {
                    q.push(x);
                    vis[x]=true;
                    db1++;
                    if(db1>1 && !ketto)
                    {
                        ketto=true;
                        l=q.size()-2;
                        r=q.size()-1;
                    }
                }
            }
            db++;
        }
        if(db<n)
        {
            return -1;
        }
        if(!ketto)
        {
            return 1;
        }
        return 2;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>k;
    befok.resize(n+1,0);
    g.resize(n+1);
    vis.resize(n+1,0);
    db=0;
    for(int i=1;i<=k;i++)
    {
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        befok[v]++;
    }
    int m=bfs();
    if(m==-1)
    {
        cout<<0<<'\n';
    }else if(m==1)
    {
        cout<<1<<'\n';
        for(int x:mo)
        {
            cout<<x<<" ";
        }
    }else
    {
        cout<<2<<'\n';
        for(int x:mo)
        {
            cout<<x<<" ";
        }
        cout<<'\n';
        for(int i=0;i<=n-1;i++)
        {
            if(i!=l && i!=r)
            {
                cout<<mo[i]<<" ";
            }else if(i==l)
            {
                cout<<mo[r]<<" ";
            }else if(i==r)
            {
                cout<<mo[l]<<" ";
            }
        }
    }
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base28/50
1Elfogadva0/02ms1812 KiB
2Elfogadva0/01ms1796 KiB
3Elfogadva0/093ms15856 KiB
4Hibás válasz0/21ms4164 KiB
5Elfogadva3/31ms4168 KiB
6Hibás válasz0/31ms4176 KiB
7Elfogadva3/31ms4184 KiB
8Elfogadva1/11ms4180 KiB
9Elfogadva3/31ms4184 KiB
10Hibás válasz0/33ms4260 KiB
11Hibás válasz0/32ms4296 KiB
12Elfogadva1/12ms4320 KiB
13Elfogadva2/22ms4340 KiB
14Elfogadva3/32ms4368 KiB
15Elfogadva1/179ms14184 KiB
16Elfogadva3/394ms24052 KiB
17Elfogadva5/554ms22668 KiB
18Elfogadva1/1141ms32008 KiB
19Elfogadva2/282ms20880 KiB
20Hibás válasz0/3158ms34384 KiB
21Hibás válasz0/4131ms36220 KiB
22Hibás válasz0/4115ms38056 KiB