Cod sursa(job #2130713)

Utilizator AndreiStanescuAlloys Nokito AndreiStanescu Data 13 februarie 2018 20:55:00
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.3 kb
#include<bits/stdc++.h>
#define N 100005
#define M 200005
using namespace std;

vector <int> G[N],GT[N];
int n,m;

inline void read()
{
    freopen("ctc.in","rt",stdin);
    scanf("%d%d",&n,&m);
   // memset(a,0,sizeof(a));
    int i,x,y;
    for(i=1;i<=m;++i)
    {
        scanf("%d%d",&x,&y);
        //a[x][y]=1;
        G[x].push_back(y);
        GT[y].push_back(x);
    }

}

/*void floyd()
{
    int i,j,k;
    for(k=1;k<=n;k++)
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
           if(!a[i][j]) a[i][j]=a[i][k]*a[k][j];

}*/
int cn;
vector<int> q;
vector<int> C[N];
int viz[N];

/*void bfs(int i)
{
    int x,j,k,nod;
    q.push(i);
    viz[++cn]=i;
    while(!q.empty())
    {
        x=q.front();
       q.pop();
       C[cn].push_back(x);
       //if(!viz[x])
       for(j=1;j<=n;j++)
        //if(a[x][j] && a[j][x] && !viz[j] && j!=x)
       {//C[cn].push_back(j);
           viz[j]=cn;
           q.push(j);
       }
    }

}*/




void solve()
{
    int i,j;
    for(int i=1;i<=n;i++)
    {for(int j=1;j<=n;j++)
   // cout<<a[i][j]<<' ';
    cout<<endl;
    }
    for(int i=1;i<=n;++i)
    if(!viz[i])
    {
        //bfs(i);
        //viz[i]=1;
    }
   // cout<<cn;
    for(i=1;i<=cn;i++)
    {for(j=0;j<C[i].size();j++)
        cout<<C[i][j]<<' ';
        cout<<endl;
    }
}

stack<int> s;
vector<int> sol[N];
int nc;
void dfs(int nod)
{
    int i;
    s.push(nod);

    //cout<<nod<<' ';
    viz[nod]=1;
    for(i=0;i<G[nod].size();i++)
        if(!viz[G[nod][i]])
          dfs(G[nod][i]);

    q.push_back(nod);

}

void dft(int nod)
{
    viz[nod]=0;
    sol[nc].push_back(nod);
    for(int i=0;i<GT[nod].size();i++)
        if(viz[GT[nod][i]])
            dft(GT[nod][i]);

}


int main()
{
    int i,j,x;
    read();
    //floyd();
    freopen("ctc.out","wt",stdout);

    for(i=1;i<=n;i++)
     if(!viz[i])
        dfs(i);

    while(!q.empty())
    {
        x=q.back();
        q.pop_back();
        if(viz[x]==1)
            {
                ++nc;
                dft(x);
            //cout<<'\n';
            }
    }

    cout<<nc<<'\n';
    for(i=1;i<=nc;i++)
    {
        for(j=0;j<sol[i].size();j++)
        cout<<sol[i][j]<<' ';
        cout<<'\n';
    }


}