13172022-05-11 20:01:17nkdorka1212Testnevelés óracpp11Wrong answer 28/50141ms38056 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;
}
SubtaskSumTestVerdictTimeMemory
base28/50
1Accepted0/02ms1812 KiB
2Accepted0/01ms1796 KiB
3Accepted0/0104ms15892 KiB
4Wrong answer0/21ms4168 KiB
5Accepted3/31ms4168 KiB
6Wrong answer0/31ms4176 KiB
7Accepted3/31ms4176 KiB
8Accepted1/11ms4184 KiB
9Accepted3/31ms4188 KiB
10Wrong answer0/32ms4264 KiB
11Wrong answer0/32ms4296 KiB
12Accepted1/12ms4312 KiB
13Accepted2/22ms4340 KiB
14Accepted3/32ms4388 KiB
15Accepted1/185ms14188 KiB
16Accepted3/3101ms24088 KiB
17Accepted5/546ms22672 KiB
18Accepted1/1141ms32020 KiB
19Accepted2/268ms20872 KiB
20Wrong answer0/3108ms34368 KiB
21Wrong answer0/4112ms36224 KiB
22Wrong answer0/4112ms38056 KiB