Cod sursa(job #781050)

Utilizator lauraxxxLaura Balan lauraxxx Data 23 august 2012 00:31:46
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.86 kb
//Algoritmul lui Kosajaru

#include <stdio.h>
#include <vector>
#define maxEdges 100000 + 1

using namespace std;

vector<int> G[maxEdges], GT[maxEdges], SCC[maxEdges];
bool visited[maxEdges];
int blackEdges, numSCC, st[maxEdges];

void DF1(int node)
{
	vector <int> :: iterator it;
	
	visited[node] = 1;
	for (it = GT[node].begin(); it != GT[node].end(); it ++)
		if (!visited[*it])
			DF1(*it);
	st[++blackEdges] = node; 
}

void DF2(int node)
{
	vector <int> :: iterator it;
	
	visited[node] = 1;
	SCC[numSCC].push_back(node);
	
	for (it = G[node].begin(); it != G[node].end(); it ++)
		if (!visited[*it])
			DF2(*it);
}

int main()
{
	vector <int> :: iterator it;
	int i, x, y, N, M;
	
	freopen("ctc.in", "r", stdin);
	freopen("ctc.out", "w", stdout);
	
	//Citesc graful si construiesc graful transpus
	scanf("%d%d", &N, &M);
	for (i = 1; i <= M; i ++)
	{
		scanf("%d%d", &x, &y);
		G[x].push_back(y);
		GT[y].push_back(x);
	}
	
	//Calculez timpii de terminare pentru fiecare nod din graful transpus
	for (i = 1; i <= N; i ++)
		if (visited[i] == false)
			DF1(i);
	
	//Resetez vectorul de vizitare pe 0.
	for (i = 1; i <= N; i ++)
		visited[i] = 0;
	
	//Stiu sigur ca prima componenta tare conexa va fi cea cu cel mai mare timp de terminare. 
	//(nodul este "source" in graful transpus, asa ca devine "sink" in graful original). 
	//Dupa eliminarea componentei tare conexe, urmatoarea va fi exact cea cu cel mai mare timp terminal
	//care nu a fost deja eliminata. Deci e destul sa parcurg nodurile in ordinea descrescatoare timpilor terminali
	
	for (i = N; i >= 1; i --)
		if (!visited[st[i]])
		{
			++numSCC;
			DF2(st[i]);
		}
		
	//Afisez solutia
	printf("%d\n", numSCC);
	for (i = 1; i <= numSCC; i ++, printf("\n"))
		for (it = SCC[i].begin(); it != SCC[i].end(); it ++)
			printf("%d ", *it);

	return 0;
}