Cod sursa(job #1944329)

Utilizator titusuTitus C titusu Data 29 martie 2017 08:49:47
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <iostream>
#include <vector>
#include <stack>

using namespace std;
#define pb push_back
int n, m, nrc;
vector<int> G[101], G1[101], v, M[101];
stack<int> stk;
void Df(int x);
void Df1(int x);
int main()
{
    cin >> n >> m;
    int x, y;
    for(; m; --m) {
        cin >> x >> y;
        G[x].pb(y);
        G1[y].pb(x);
    }

    v.assign(n+1,0);
    for(int i = 1; i <= n; i++)
        if(!v[i]) Df(i);
    v.assign(n+1,0);
    while(!stk.empty()) {
        x = stk.top(); stk.pop();
        if(!v[x]) {
            nrc++;
            Df1(x);

        }
    }
    cout << nrc << "\n";
    for(int i = 1; i <= nrc; i++)
    {
        for(auto p: M[i])
            cout << p << " ";
        cout << '\n';
    }
    return 0;
}
void Df(int x)
{
    v[x] = 1;
    for(auto p: G[x])
        if(!v[p]) Df(p);
    stk.push(x);
}
void Df1(int x)
{
    v[x] = nrc;
    M[nrc].push_back(x);
    for(auto p: G1[x])
        if(!v[p]) Df1(p);
}