Cod sursa(job #1519410)

Utilizator cristian.caldareaCaldarea Cristian Daniel cristian.caldarea Data 7 noiembrie 2015 12:22:11
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
// storngly linked(connected) verticles - componente tare conexe
#include <iostream>
#include <stack>
#include <fstream>
#include <vector>
using namespace std;

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

using VI = vector<int>;

int n, m, nrc;
vector<VI> G1, G2, C;

vector<bool> s;
stack<int> st;

void Read();
void Df1(int x);
void Df2(int x);
int main()
{
    Read();
    for ( int i = 1; i <= n; i++ )
        if ( !s[i] )
            Df1(1);

    s.assign(n+1, 0);
    int x;
    while (!st.empty())
    {
        x = st.top();
        st.pop();
        if ( s[x] != 1 )
        {
            nrc++;
            Df2(x);
        }
    }
    fout << nrc << '\n';
    for ( int i = 1; i <= nrc; i++ )
    {
        for ( const int& y : C[i] )
            fout << y << ' ';
        fout << '\n';
    }

    fin.close();
    fout.close();
    return 0;
}

void Read()
{
    fin >> n >> m;
    G1 = vector<VI>(n+1);
    G2 = vector<VI>(n+1);
    C = vector<VI>(n+1);
    s = vector<bool>(n+1);
    int x, y;

    for ( int i = 1; i <= m; i++ )
    {
        fin >> x >> y;
        G1[x].push_back(y);
        G2[y].push_back(x);
    }
}

void Df1(int x)
{
    s[x] = 1;
    for ( const int& y : G1[x] )
    {
        if ( s[y] != 1 )
            Df1(y);
    }
    st.push(x);
}
void Df2(int x)
{
    s[x] = 1;
    C[nrc].push_back(x);
    for ( const int& y : G2[x] )
    {
        if ( s[y] != 1 )
            Df2(y);
    }
}