Cod sursa(job #1910798)

Utilizator geralt_of_riviajohn nathalis geralt_of_rivia Data 7 martie 2017 18:20:29
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <fstream>

using namespace std;
ifstream cin ("ctc.in");
ofstream cout ("ctc.out");
int start[100010],startr[100010];
int n,m,o,st[100010],nr;
int used[100010];
struct bla
{
    int nod,urm;
} t[200010],tr[200010];
void read ()
{ int a,b,k=0;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>a>>b;
        t[++k].nod=b; t[k].urm=start[a]; start[a]=k;
        tr[++k].nod=a; tr[k].urm=startr[b]; startr[b]=k;
    }
}
void dfs_first (int nod)
{
    if(used[nod]==1) return;
    used[nod]=1;
    for(int x=start[nod];x;x=t[x].urm)
        dfs_first(t[x].nod);
    st[++o]=nod;
}
void dfs_second (int nod)
{
    if(used[nod]==1) return;
    used[nod]=1;
    for(int x=startr[nod];x;x=tr[x].urm)
        dfs_second(tr[x].nod);
}
void dfs_tirth (int nod)
{
    if(used[nod]==1) return;
    used[nod]=1;
    for(int x=startr[nod];x;x=tr[x].urm)
        dfs_tirth(tr[x].nod);
    cout<<nod<<" ";
}
void solve()
{
    for(int i=1;i<=n;i++)
       if(used[i]==0) dfs_first(i);
    for(int i=1;i<=n;i++) used[i]=0;
    for(int i=o;i>=1;i--)
        if(used[st[i]]==0) dfs_second(st[i]),nr++;
    for(int i=1;i<=n;i++) used[i]=0;
    cout<<nr<<"\n";
    for(int i=o;i>=1;i--)
        if(used[st[i]]==0)
            dfs_tirth(st[i]),cout<<"\n";
}
int main()
{
    read();
    solve();
    cin.close();
    cout.close();
    return 0;
}