Cod sursa(job #1632230)

Utilizator tothalToth Alexandru tothal Data 5 martie 2016 23:04:48
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <fstream>
#include <vector>
#define Nmax 100005
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector <int> G[Nmax];
vector <int> GT[Nmax];
vector <int> ctc[Nmax];
int n,m;
int nrctc,st[Nmax],top;
int use[Nmax];
void read()
{int x,y;
fin>>n>>m;
for(int i=1;i<=m;i++)
{fin>>x>>y;
    G[x].push_back(y);
    GT[y].push_back(x);
}
}

void dfsp(int nod)
{
    use[nod]=1;
    for(int i=0;i<(int)G[nod].size();i++)
        if(!use[G[nod][i]])
            dfsp(G[nod][i]);
    st[++top]=nod;
}
void dfsm(int nod)
{
    use[nod]=0;
    ctc[nrctc].push_back(nod);

    for(int i=0;i<(int)GT[nod].size();i++)
        if(use[GT[nod][i]])
            dfsm(GT[nod][i]);
}

void solve()
{
    for(int i=1;i<=n;i++)
        if(!use[i])
            dfsp(i);
    for(int i=n; i>=1;i--)
    {
        if(use[st[i]]==1)
            {   nrctc++;
                dfsm(st[i]);
            }
    }
}
void print()
{
    fout<<nrctc<<"\n";
    for(int i=1;i<=nrctc;i++)
    {
        for(int j=0;j<(int)ctc[i].size();j++)
            fout<<ctc[i][j]<<" ";
        fout<<"\n";
    }
}
int main()
{
    read();
    solve();
    print();
    return 0;
}