Cod sursa(job #1437840)

Utilizator roberta9533Pavel Roberta roberta9533 Data 18 mai 2015 18:32:19
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector <int> G[100001],Gt[100001],C[100001],U;
int viz[100001];
static int w=0;

void st(int x)
{
    viz[x]=1;
    for(int i=0;i<G[x].size();i++)
        if(viz[G[x][i]]==0)
            st(G[x][i]);
    U.push_back(x);
}

void dfs(int x)
{
    C[w].push_back(x);
    viz[x]=1;
    for(int i=0;i<Gt[x].size();i++)
        if(viz[Gt[x][i]]==0)
            dfs(Gt[x][i]);
}

int main()
{
    int n,m,x,y,ok,i;
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y;
        G[x].push_back(y);
        Gt[y].push_back(x);
    }
    for(i=1;i<=n;i++)
        if(viz[i]==0)
            st(i);
    for(i=1;i<=n;i++)
        viz[i]=0;
    for(i=n-1;i>=0;i--)
        if(viz[U[i]]==0)
        {
            w++;
            dfs(U[i]);
        }
    g<<w<<endl;
    for(i=1;i<=w;i++)
    {
        for(int j=0;j<C[i].size();j++)
            g<<C[i][j]<<" ";
        g<<endl;
    }
    return 0;
}