Cod sursa(job #2127338)

Utilizator titusuTitus C titusu Data 10 februarie 2018 16:02:36
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <set>

using namespace std;

fstream fin("ctc.in", ios::in), fout("ctc.out", ios::out);

vector<vector<int> > G, GT;

int n , m , contor , nrs;

vector<bool> V;
vector<int> S, R;

void read()
{
    fin >> n >> m;
    G = GT = vector<vector<int>>(n + 1);
    V = vector<bool> (n + 1, false);
    R = vector<int> (n + 1 , 0);
    for(int i = 1 ; i <= m ; i++)
    {
        int a , b;
        fin >> a >> b;
        G[a].push_back(b);
        GT[b].push_back(a);
    }

}
void dfs(int k)
{
    V[k] = true;
    for(auto x : G[k])
        if(!V[x]) 
			dfs(x);
    S.push_back(k);
}
void dfsGT(int k, int root)
{
    R[k] = root;
    V[k]=1;
    for(auto x: GT[k])
        if(! V[x])
			dfsGT(x, root);

}
int main()
{

    read();
    for(int i = 1 ; i <= n ; i ++)
        if(! V[i]) 
			dfs(i);
			
    V = vector<bool> (n + 1, false);
    
    for(vector<int>::reverse_iterator it = S.rbegin() ; it != S.rend() ; it ++)
        if(!V[*it]) {
                dfsGT(* it, * it);
        }
    vector<vector<int>> C;
	vector<int> P = vector<int> (n + 1, 0);
	for(int i = 1 ; i <= n ; i ++)
		if(P[R[i]] == 0)
		{
			C.push_back(vector<int>(0));
			C.back().push_back(i);
			P[R[i]] = C.size();
		}
		else
			C[P[R[i]]-1].push_back(i);
	fout << C.size() << "\n";
	for(auto M : C)
	{
		for(auto x : M)
			fout << x << " ";
		fout << "\n";
	}
    return 0;
}