Cod sursa(job #2087103)

Utilizator titusTitus A titus Data 12 decembrie 2017 22:02:06
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
///50p
#include <bits/stdc++.h>
#define NM 100001
using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

int n, ctc[NM], nrc;
int Plus[NM], Minus[NM];
vector <int> G[NM], GT[NM];
stack <int> st;

void df1(int x)
{
    Plus[x] = 1;
    for(int i=0; i < (int)G[x].size(); ++i)
        if(Plus[G[x][i]] == 0)
            df1(G[x][i]);
    st.push(x);
}

void df2(int x) ///graful transpus
{
    Minus[x] = nrc;
    for(int i=0; i < (int)GT[x].size(); ++i)
        if(Minus[GT[x][i]] == 0)
            df2(GT[x][i]);
}

int main()
{
    int i , j , m;
    f >> n >> m;
    while( m-- ) {
        f >> i >> j;
        G[i].push_back(j);
        GT[j].push_back(i); ///graful transpus
    }

    for(int i = 1 ; i <= n ; ++i)
        if (Plus[i] == 0) df1(i);

    while(!st.empty()){
        int k = st.top();
        st.pop();
        if (Minus[k] == 0) {
            nrc++;
            df2(k);
        }
    }

    g << nrc << "\n";
    for(int i=1; i<=nrc; ++i){
        for(int j=1; j<=n; ++j)
            if (Minus[j] == i) g << j << " ";
        g << '\n';
    }

    return 0;
}