Cod sursa(job #1729098)

Utilizator ade_tomiEnache Adelina ade_tomi Data 14 iulie 2016 11:11:47
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include<iostream>
#include<fstream>
#include<vector>
#define NMAX 100003
using namespace std;
int st[NMAX],viz[NMAX],viz2[NMAX],n,m,i,p,nr;
vector<int>v[NMAX],g[NMAX],sol[NMAX];
void dfs1(int k)
{


//cout<<k<<" ";
    viz[k]=1;
    for(int i=0;i<v[k].size();i++)
        if(viz[v[k][i]]==0)
            dfs1(v[k][i]);
    nr++;
    st[nr]=k;
}
void dfs2(int k)
{

    viz2[k]=1;
    sol[p].push_back(k);
    for(int i=0;i<g[k].size();i++)
    {

        if(viz2[g[k][i]]==0)
            dfs2(g[k][i]);
    }
}
int main()
{

    ifstream cin("ctc.in");
    ofstream cout("ctc.out");
    cin>>n>>m;
    int a,b;
    for(i=1;i<=m;i++)
    {

        cin>>a>>b;
        v[a].push_back(b);
        g[b].push_back(a);
    }
    for(i=1;i<=n;i++)
        if(viz[i]==0)
            dfs1(i);




    for(i=nr;i>=1;i--)
    {
       // cout<<st[i]<<" ";
        if(viz2[st[i]]==0){
            p++;
            dfs2(st[i]);
        }
    }
    cout<<p<<"\n";
    for(i=1;i<=p;i++)
    {
        for(int j=0;j<sol[i].size();j++)
            cout<<sol[i][j]<<" ";
        cout<<"\n";
    }
    return 0;
}