Cod sursa(job #2087110)

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

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

int n, nrc;
int Plus[NM], Minus[NM];
vector <int> G[NM], GT[NM], ctc[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);
        }
    }
    for(int i=1; i <= n; ++i)
        ctc[Minus[i]].push_back(i);

    g << nrc << "\n";
    for(int i=1; i <= nrc; ++i){
        for(int j=0; j < (int) ctc[i].size(); ++j)
            g << ctc[i][j] << " ";
        g << '\n';
    }

    return 0;
}