Cod sursa(job #1685360)

Utilizator RobertSSamoilescu Robert RobertS Data 11 aprilie 2016 17:16:17
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.65 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <string.h>


struct Node {
	int index, lowlink;
	std::vector<int> list;

	Node()
	:index(-1), lowlink(-1)
	{}
	
};


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


std::stack<int> st;
int level = 0;

std::vector<std::vector<int> >comp;


void dfs(int node, std::vector<Node> &g, bool *on_stack) {
	
	on_stack[node] = true;
	g[node].index = level;
	g[node].lowlink = level;

	level++;

	st.push(node);

	for (size_t i = 0; i < g[node].list.size(); i++) {
		if (g[g[node].list[i]].index == -1) {
			dfs(g[node].list[i], g, on_stack);
			g[node].lowlink = std::min(g[node].lowlink, g[g[node].list[i]].lowlink);
		} else if (on_stack[g[node].list[i]]) {
			g[node].lowlink = std::min(g[node].lowlink, g[g[node].list[i]].lowlink);
		}
	}


	if (g[node].lowlink == g[node].index) {
		std::vector<int> v;
		int top;
		do {
			top = st.top();
			st.pop();
			on_stack[top] = false;
			v.push_back(top);
		}while (top != node);

		comp.push_back(v);
	}
	
}


void solve(std::vector<Node> &g, int N) {
	
	bool on_stack[N + 1];
	memset(on_stack, false, sizeof(on_stack));

	for (int i = 1; i <= N; i++) {
		if (g[i].index == -1)
			dfs(i, g, on_stack);
	}

	fout << comp.size() << '\n';

	for (size_t i = 0; i < comp.size(); i++) {
		for (size_t j = 0; j < comp[i].size(); j++) {
			fout << comp[i][j] << " ";
		}

		fout << '\n';
	}
}


int main() {

	int N, M;
	fin >> N >> M;
	
	std::vector<Node> graph(N + 1);

	for (int i = 0; i < M; i++) {
		int x, y;
		fin >> x >> y;
		graph[x].list.push_back(y);
	}

	bool viz[N + 1];
	memset(viz, false, sizeof(viz));

	solve(graph, N);

	

	return 0;
}