Cod sursa(job #1328996)

Utilizator andreiulianAndrei andreiulian Data 28 ianuarie 2015 22:25:11
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include<fstream>
#include<vector>
#define pb push_back
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
int N,M,S[100005],u,us;
bool viz[100005];
vector <int> s[100005],p[100005],sol[100005];
void ad_stiva(int i);
void ad_transpus(int i);
int main()
{
    in>>N>>M;
    int a,b,i,j;
    for(i=1;i<=N;++i) s[i].pb(0),p[i].pb(0);
    for(i=1;i<=M;++i)
    {
        in>>a>>b;
        s[a].pb(b);
        s[a][0]++;
        p[b].pb(a);
        p[b][0]++;
    }
    for(i=1;i<=N;++i) if(!viz[i]) ad_stiva(i);
    for(i=N;i>0;--i)
    {
        if(viz[S[i]])
        {
            ++us;
            sol[us].pb(0);
            ad_transpus(S[i]);
        }
    }
    out<<us<<'\n';
    for(i=1;i<=us;++i)
    {
        for(j=1;j<=sol[i][0];++j)
            out<<sol[i][j]<<' ';
        out<<'\n';
    }
}
void ad_stiva(int i)
{
    int k;
    viz[i]=1;
    for(k=1;k<=s[i][0];++k)
    {
        if(!viz[s[i][k]])
        {
            viz[s[i][k]]=1;
            ad_stiva(s[i][k]);
        }
    }
    S[++u]=i;
}
void ad_transpus(int i)
{
    sol[us].pb(i);
    ++sol[us][0];
    viz[i]=0;
    int k;
    for(k=1;k<=p[i][0];++k)
    {
        if(viz[p[i][k]])
        {
            ad_transpus(p[i][k]);
        }
    }
}