Mai intai trebuie sa te autentifici.

Cod sursa(job #1519592)

Utilizator cristian.caldareaCaldarea Cristian Daniel cristian.caldarea Data 7 noiembrie 2015 16:04:58
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include <iostream>
#include <stack>
#include <fstream>
#include <algorithm>
#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(i);

    s.assign(n+1, 0);
    int x;
    while (!st.empty())
    {
        x = st.top();
        st.pop();

        if ( !s[x] )
        {
            nrc++;
            Df2(x);


        }
        //fout << x << ' ' << nrc << '\n';
    }
    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;

   while (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 )
        {
           // fout << x << ' ' << y << '\n';
            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);

        }

    }
}