Cod sursa(job #1707430)

Utilizator contnouAndrei Pavel contnou Data 25 mai 2016 03:35:13
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.78 kb
#include<fstream>
#include<iostream>
#include<vector>
#include<cstring>

using namespace std;

#define MAXN 100005

struct SCCLists {
	int size;
	SCCLists() {
		size = 0;
	}
	vector<int> scc[MAXN];
};

struct Graph {
	int n, m;
	vector<int> adj[MAXN];
};

	ifstream f("ctc.in");
	ofstream g("ctc.out");

void computeScc(Graph& G, int source, int* visited, int* index, int* lowlink, int* stack, int &time, SCCLists& scc) {
	//
	visited[source] = 1;
	index[source] = ++time;
	lowlink[source] = time;

	stack[++stack[0]] = source;

	for (int it = 0; it < G.adj[source].size(); it++) {
		if (!visited[G.adj[source][it]]) {
			computeScc(G, G.adj[source][it], visited, index, lowlink, stack, time, scc);
		}
	}
	
	int min = index[source];

	for (int it = 0; it < G.adj[source].size(); it++) {
		min = min > lowlink[G.adj[source][it]] ? lowlink[G.adj[source][it]] : min;
	}

	lowlink[source] = min;
	if (lowlink[source] >= index[source]) {
		scc.size++;
		while (stack[stack[0]] != source) {
			scc.scc[scc.size].push_back(stack[stack[0]]);
			stack[0]--;
		}

		stack[0]--;
		scc.scc[scc.size].push_back(source);
	}
}

int main() {
	//
	SCCLists scc;
	int visited[MAXN], index[MAXN], lowlink[MAXN], stack[MAXN];
	Graph G;
	int time = 0;

	memset(visited, 0, sizeof(visited));
	memset(index, 0, sizeof(index));
	memset(lowlink, 0, sizeof(lowlink));
	memset(stack, 0, sizeof(stack));

	f >> G.n >> G.m;

	for (int i = 1; i <= G.m; i++) {
		int x, y;
		f >> x >> y;
		G.adj[x].push_back(y);
	}

	computeScc(G, 1, visited, index, lowlink, stack, time, scc);

	g << scc.size << "\n";
	for (int it = 1; it <= scc.size; it++) {
		for (int jt = 0; jt < scc.scc[it].size(); jt++) {
			g << scc.scc[it][jt] << " ";
		}
		g << "\n";
	}

	return 0;
}