13162022-05-11 19:58:48nkdorka1212Testnevelés óracpp11Wrong answer 26/50125ms35940 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<<-1<<'\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
base26/50
1Accepted0/02ms1852 KiB
2Accepted0/01ms1844 KiB
3Accepted0/0111ms15940 KiB
4Wrong answer0/21ms4236 KiB
5Accepted3/31ms4232 KiB
6Wrong answer0/31ms4244 KiB
7Accepted3/31ms4224 KiB
8Wrong answer0/11ms4232 KiB
9Accepted3/31ms4264 KiB
10Wrong answer0/32ms4348 KiB
11Wrong answer0/32ms4452 KiB
12Wrong answer0/12ms4464 KiB
13Accepted2/22ms4484 KiB
14Accepted3/32ms4436 KiB
15Accepted1/187ms14232 KiB
16Accepted3/398ms24164 KiB
17Accepted5/543ms22800 KiB
18Accepted1/1125ms31080 KiB
19Accepted2/285ms19888 KiB
20Wrong answer0/3120ms33452 KiB
21Wrong answer0/4122ms34064 KiB
22Wrong answer0/4119ms35940 KiB