Cod sursa(job #999843)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 21 septembrie 2013 15:52:06
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <cstdio>
#include <vector>
#include <stack>
#include <bitset>

using namespace std;
const int Nmax = 100005;

vector<int> G[ Nmax ],Gt[ Nmax ],answer[ Nmax ];
stack <int> S;
bitset <Nmax> used;
int N,M,ctc;

void read()
{
    scanf("%d%d",&N,&M);
    int x,y;
    for(int i = 1; i <= M; ++i)
    {
        scanf("%d%d",&x,&y);
        G[x].push_back(y);
        Gt[y].push_back(x);
    }
}

void DFS(int nodc)
{
    vector<int>::iterator it;
    used.set(nodc);
    for(it=G[nodc].begin();it!=G[nodc].end();++it)
        if(used[*it]==false)
            DFS(*it);
    S.push(nodc);
}

void DFS_t(int nodc)
{
    vector<int>::iterator it;
    used.set(nodc);
    answer[ctc].push_back(nodc);
    for(it=Gt[nodc].begin();it!=Gt[nodc].end();++it)
        if(used[*it]==false)
            DFS_t(*it);
}

void solve()
{
    for(int i = 1; i <= N; ++i)
        if(used[i]==false) DFS(i);
    used.reset();
    while(!S.empty())
    {
        if(used[ S.top() ] == false)
        {
            DFS_t(S.top());
            ++ctc;
        }
        S.pop();
    }
}

void print()
{
    printf("%d\n",ctc);
    for(int i = 0; i < ctc; ++i)
    {
        for(vector<int>::iterator it=answer[i].begin();it!=answer[i].end();++it)
            printf("%d ",*it);
        printf("\n");
    }
}

int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);

    read();
    solve();
    print();
    return 0;
}