Cod sursa(job #1474050)

Utilizator pas.andreiPopovici Andrei-Sorin pas.andrei Data 20 august 2015 19:54:29
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include <iostream>
#include <fstream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <set>
//#include <cstring>
#include <cmath>
#include <bitset>
#include <utility>
#include <stack>
#define MAXN 100005

using namespace std;

vector<int> v[MAXN], compConexa;
vector<vector<int> > final;
bool inStack[MAXN];
int index[MAXN], lowlink[MAXN], nrindex;
stack<int> S;

void tarjan(int n);

int main() {
	int n, m, x, y, i, j;

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

	fin >> n >> m;

	for (i = 0; i < m; ++i) {
		fin >> x >> y;

		v[x].push_back(y);
	}

	for (i = 1; i <= n; ++i) {
		if (index[i] == 0)
			tarjan(i);
	}

	fout << final.size() << '\n';
	for (i = 0; i < final.size(); ++i) {
		for (j = 0; j < final[i].size(); ++j)
			fout << final[i][j] << ' ';

		fout << '\n';
	}

	return 0;
}

void tarjan(int n) {
	++nrindex;
	index[n] = lowlink[n] = nrindex;
	S.push(n);
	inStack[n] = true;

	vector<int>::iterator it;
	for (it = v[n].begin(); it != v[n].end(); ++it) {
		if (index[*it] == 0) {
			tarjan(*it);
			lowlink[n] = min(lowlink[n], lowlink[*it]);
		}
		else if (inStack[*it] == true)
			lowlink[n] = min(lowlink[n], lowlink[*it]);
	}

	if (index[n] == lowlink[n]) {
		compConexa.clear();
		int node;

		do {
			node = S.top();
			S.pop();
			inStack[node] = 0;
			compConexa.push_back(node);
		} while (node != n);

		final.push_back(compConexa);
	}
}