Cod sursa(job #1645628)

Utilizator alevasluialeHuhurez Marius alevasluiale Data 10 martie 2016 13:06:59
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <cstdio>
#include <bitset>
#include <vector>
using namespace std;
const int N=100001;
vector<int>H[N],P[N],Q[N];
bitset<N>viz;
int post[N],nr,n,m;
void read()
{
    int i,j;
    scanf("%d%d",&n,&m);
    while(m--)
    {
        scanf("%d%d",&i,&j);
        H[i].push_back(j);
        Q[j].push_back(i);
    }
}
void dfs(int nod)
{
    viz[nod]=1;
    for(vector<int>::iterator it=H[nod].begin();it!=H[nod].end();it++)
    {
        if(viz[*it]==0) dfs(*it);
    }
    post[nr]=nod;nr++;
}
void conexe()
{
    nr=1;
    for(int i=1;i<=n;i++)
    {
        if(viz[i]==0) dfs(i);
    }
    viz.reset();
}
void dfst(int nod,int x)
{
    viz[nod]=1;
    for(vector<int>::iterator it=Q[nod].begin();it!=Q[nod].end();it++)
    {
        if(viz[*it]==0) dfst(*it,x);
    }
    P[x].push_back(nod);
}
void tareconexe()
{
    nr=0;
    for(int i=n;i>=1;i--)
    {
        if(viz[post[i]]==0) {nr++;dfst(post[i],nr);}
    }
}
void write()
{
    printf("%d\n",nr);
    for(int i=1;i<=nr;i++)
    {
        for(vector<int>::iterator it=P[i].begin();it!=P[i].end();it++) printf("%d ",*it);
        printf("\n");
    }
}
int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    read();
    conexe();
    tareconexe();
    write();
}