Cod sursa(job #1442554)

Utilizator rangerChihai Mihai ranger Data 25 mai 2015 20:12:54
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include<fstream>
#include<vector>

using namespace std;

ifstream cin("ctc.in");
ofstream cout("ctc.out");

const int NMAX = 100004;
int N, M, i,j,x,y, NR;
vector<int> g[NMAX], gr[NMAX], scc[NMAX];
vector<int> used(NMAX,0), order;

void dfs1(int v)
{
    used[v]=1;
    for (int i=0;i<g[v].size();i++)
        if (!used[g[v][i]]) dfs1(g[v][i]);
    order.push_back(v);
}

void dfs2(int v)
{
    used[v]=1;
    scc[NR].push_back(v);
    for(int i=0;i<gr[v].size();i++)
        if (!used[gr[v][i]]) dfs2(gr[v][i]);
}

int main()
{
    cin >> N >> M;
    while (M--)
    {
        cin >> x >> y;
        g[x]. push_back(y);
        gr[y].push_back(x);
    }
    for (i=1;i<=N;i++)
        if (!used[i]) dfs1(i);

    used.assign(N+1,0);
    for (i=N-1;i>=0;i--)
        if (!used[order[i]])
    {
        ++NR;
        dfs2(order[i]);
    }
    cout << NR << '\n';
    for (i=1;i<=NR;i++)
    {

        for (j=0;j<scc[i].size();j++)cout<<scc[i][j]<<' ';
        cout<<'\n';
    }
    return 0;
}