Cod sursa(job #1346591)

Utilizator CiurezAndreiCiurez Marius-Andrei CiurezAndrei Data 18 februarie 2015 13:39:50
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <fstream>
#include <stack>
#include <vector>
#include <bitset>

using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");


int nivel[100010], low[100010];
int i, j, niv, n, m, x, y, nr, w;
vector <int> L[100010], P[100010];
stack <int> S;
bitset <100010> v;
bitset <100010> X;
void dfs(int nod){
    v[nod] = 1;
    nivel[nod] = low[nod] = niv;
    niv++;
    S.push(nod);
    X[nod] = 1;
    for(int i = 0; i < L[nod].size(); i ++){
        if(v[ L[nod][i] ] == 0){
            dfs(L[nod][i]);
            low[nod] = min(low[nod], low[ L[nod][i] ]);
        }
        if( X[ L[nod][i] ] )
            low[nod] = min(low[nod], low[ L[nod][i] ]);
    }
        if(low[nod] == nivel[nod]){
            nr++;
            do{
                X[ S.top() ] = 0;
                w = S.top();
                S.pop();
                P[nr].push_back( w );
            }while(w != nod);

        }


}
int main()
{
    fin >> n >> m;
    for(i = 1; i <= m; i++)
        {
            fin >> x >> y;
            L[x].push_back(y);
        }
    niv = 1;
    for(i = 1; i <= n; i ++)
        if(!v[i])
            dfs(i);
    fout << nr << '\n';
    for(i = 1; i <= nr; i ++){

        for(j = 0; j < P[i].size(); j ++)
            fout << P[i][j] << " ";
        fout << '\n';
    }
    return 0;
}