Cod sursa(job #1613669)

Utilizator mihaimusatMihai Musat mihaimusat Data 25 februarie 2016 16:04:29
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <fstream>
#include <vector>

#define pb push_back

using namespace std;

ifstream cin("ctc.in");
ofstream cout("ctc.out");

const int nmax=100005;

vector<int>g[2*nmax],gT[2*nmax],rasp[2*nmax];
int n,m,x,y,i,nr=0,q[nmax];
bool sel[nmax];

void df(int x)
{
    sel[x]=true;

    for(vector<int>::iterator it=g[x].begin();it!=g[x].end();it++)
        if(!sel[*it]) df(*it);
    q[++nr]=x;
}

void dfT(int x)
{
    sel[x]=false;
    rasp[nr].pb(x);

    for(vector<int>::iterator it=gT[x].begin();it!=gT[x].end();it++)
        if(sel[*it]) dfT(*it);
}

int main()
{
    cin>>n>>m;
    for(i=1;i<=m;i++)
    {
        cin>>x>>y;
        g[x].pb(y);
        gT[y].pb(x);
    }
    for(i=1;i<=n;i++)
        if(!sel[i]) df(i);
    nr=0;
    for(i=n;i>=1;i--)
    {
        if(sel[q[i]]) {
        nr++;
        dfT(q[i]);
    }
    }
    cout<<nr<<'\n';
    for(i=1;i<=nr;i++)
    {
        for(vector<int>::iterator it=rasp[i].begin();it!=rasp[i].end();it++)
            cout<<*it<<" ";
        cout<<'\n';
    }
    return 0;
}