Cod sursa(job #1969335)

Utilizator trutruvasilicaHuhurez Marius trutruvasilica Data 18 aprilie 2017 13:43:14
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int Nmax=100010;
vector<int>G[Nmax];
vector<int>T[Nmax];
vector<int>comp[Nmax];
int post[Nmax],nrcomp,len;
bitset<Nmax>viz;
void dfs(int nod)
{
    viz[nod]=1;
    for(unsigned i=0;i<G[nod].size();i++)
    {
        if(viz[G[nod][i]]==0) dfs(G[nod][i]);
    }
    post[++len]=nod;
}
void dfst(int nod)
{
    viz[nod]=1;
    comp[nrcomp].push_back(nod);
    for(unsigned i=0;i<T[nod].size();i++)
    {
        if(viz[T[nod][i]]==0) dfst(T[nod][i]);
    }
}
int main()
{
    int n,m,x,y,i;
    fin>>n>>m;
    while(m--)
    {
        fin>>x>>y;
        G[x].push_back(y);
        T[y].push_back(x);
    }
    for(i=1;i<=n;i++)
    {
        if(viz[i]==0) dfs(i);
    }
    viz.reset();
    for(i=n;i>=1;i--)
    {
        if(viz[post[i]]==0)
        {
            nrcomp++;
            dfst(post[i]);
        }
    }
    fout<<nrcomp<<"\n";
    for(i=1;i<=nrcomp;i++)
    {
        for(unsigned j=0;j<comp[i].size();j++) fout<<comp[i][j]<<" ";
        fout<<"\n";
    }
}