Cod sursa(job #1708344)

Utilizator geo_furduifurdui geo geo_furdui Data 26 mai 2016 22:05:08
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <fstream>

using namespace std;
ifstream cin ("ctc.in");
ofstream cout ("ctc.out");
int t[2][200001],t1[2][200001],viz[100001],n,m,st[100001],vf,nr,start[200001],start1[200001];
void citire ()
{
    cin>>n>>m; int x,y;
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y;
        t[0][i]=y;
        t[1][i]=start[x];
        start[x]=i;
        t1[0][i]=x;
        t1[1][i]=start1[y];
        start1[y]=i;
    }
}
void dfs1 (int nod)
{
    viz[nod]=1;
    int x=start[nod];
    while(x!=0)
    {
        if(viz[t[0][x]]==0)
            dfs1(t[0][x]);
        x=t[1][x];
    }
    vf++; st[vf]=nod;
}
void dfs2 (int nod)
{
    viz[nod]=2;
     int x=start1[nod];
    while(x!=0)
    {
        if(viz[t1[0][x]]==1)
            dfs2(t1[0][x]);
        x=t1[1][x];
    }
}
void dfs3 (int nod)
{
    viz[nod]=3;
     int x=start1[nod];
     cout<<nod<<" ";
    while(x!=0)
    {
        if(viz[t1[0][x]]==2)
            dfs3(t1[0][x]);
        x=t1[1][x];
    }
}
int main()
{
    citire();
    for(int i=1;i<=n;i++)
        if(viz[i]==0)
           dfs1(i);
    for(int i=vf;i>=1;i--)
        if(viz[st[i]]==1)
          dfs2(st[i]),nr++;
          cout<<nr<<"\n";
          for(int i=vf;i>=1;i--)
              if(viz[st[i]]==2)
              dfs3(st[i]),cout<<"\n";
    return 0;
}