Cod sursa(job #1112835)

Utilizator a96tudorAvram Tudor a96tudor Data 20 februarie 2014 08:00:05
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include<cstdio>
#include<vector>
#define pb push_back
#define N_MAX 100010
using namespace std;
vector < vector<int> > Sol;
vector <int> Sol1;
vector <int> G[N_MAX];
vector <int> Gt[N_MAX];
bool used[N_MAX];
int N, ST[N_MAX];
inline void Afis ()
{
    printf("%d\n",Sol.size());
    for (int i=0;i<Sol.size();++i)
    {
        for (int j=0;j<Sol[i].size();++j)
            printf("%d ",Sol[i][j]);
        printf("\n");
    }
}
inline void DF_Trans(int nod)
{
    used[nod]=true; Sol1.pb(nod);
    for (vector <int> :: iterator it=Gt[nod].begin();it!=Gt[nod].end();++it)
        if (!used[*it]) DF_Trans(*it);
}
inline void DF(int nod)
{
    used[nod]=true; ST[++ST[0]]=nod;
    for (vector <int> :: iterator it=G[nod].begin();it!=G[nod].end();++it)
        if (!used[*it]) DF(*it);
}
inline void Load_Data(int &N)
{
    int M,x,y;
    scanf("%d%d",&N,&M);
    for (int i=1;i<=M;++i)
    {
        scanf("%d%d",&x,&y);
        G[x].pb(y); Gt[y].pb(x);
    }
    for (int i=1;i<=N;++i) used[i]=false;
}
int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    Load_Data(N); ST[0]=0;
    for (int i=1;i<=N;++i)
        if (!used[i]) DF(i);
    for (int i=1;i<=N;++i) used[i]=false;
    for (int i=ST[0];i>0;--i)
        if (!used[ST[i]]) {DF_Trans(ST[i]); Sol.pb(Sol1); Sol1.clear();}
    Afis();
    fclose(stdin); fclose(stdout);
    return 0;
}