Cod sursa(job #1474498)

Utilizator tudi98Cozma Tudor tudi98 Data 22 august 2015 03:06:01
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

const int Nmax = 100000;

int N,M,SCC = 0;
stack<int> KosarajuST;
vector<int> Comp[Nmax+1],Adj[Nmax+1],TAdj[Nmax+1];
bool seen[Nmax+1];
int comp[Nmax+1];

void Dfs1(int node)
{
    seen[node] = 1;
    for (vector<int>::iterator it = Adj[node].begin(); it != Adj[node].end(); ++it)
        if (!seen[*it])
            Dfs1(*it);
    KosarajuST.push(node);
}
 
void Dfs2(int node)
{
	comp[node] = SCC;
    Comp[SCC].push_back(node);
    for (vector<int>::iterator it = TAdj[node].begin(); it != TAdj[node].end(); ++it)
        if (!comp[*it])
            Dfs2(*it);
}
 
void Kosaraju()
{
    for (int i = 1; i <= N; ++i)
        if (!seen[i])
            Dfs1(i);
 
    while (!KosarajuST.empty())
    {
        if (!comp[KosarajuST.top()])
        {
            ++SCC;
            Dfs2(KosarajuST.top());
        }
        KosarajuST.pop();
    }   
}

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

	fin >> N >> M;
	for (int i = 1; i <= M; ++i)
	{
		int a,b;
		fin >> a >> b;
		Adj[a].push_back(b);
		TAdj[b].push_back(a);
	}

	Kosaraju();

	fout << SCC << "\n";
	for (int i = 1; i <= SCC; ++i)
	{
	    for (vector<int>::iterator it = Comp[i].begin(); it != Comp[i].end(); ++it)
	    	fout << (*it) << " ";
		fout << "\n";
	}

}