Cod sursa(job #2610556)

Utilizator _mirubMiruna-Elena Banu _mirub Data 5 mai 2020 00:39:56
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.75 kb
#include <bits/stdc++.h>
using namespace std;

const int kNmax = 100005;

class Task {
public:
	void solve() {
		read_input();
		print_output(get_result());
	}

private:
	int n;
	int m;
	// Adjacency list for the initial graph
	vector<int> adj[kNmax];
	// Adjacency list for the transposed graph
	vector<int> adj_trans[kNmax];
	// scc[i] = strongly connected component with index i
	vector<vector<int>> scc;
	// visited[i] - 1 - visited node, 0 - node not visited 
	// DFS on the initial graph -> mark with 1 the nodes
	// DFS on the transp graph -> mark with 0 the nodes
	vector<int> visited;

	// Nodes ascending on finish time
	// reverse(topsort) -> the actual topsort
	vector<int> topsort;


	void read_input() {
		ifstream fin("ctc.in");
		fin >> n >> m;
		visited = vector<int>(n + 1, 0);
		for (int i = 1, x, y; i <= m; i++) {
			fin >> x >> y;
			adj[x].push_back(y);
			adj_trans[y].push_back(x);
		}
		fin.close();
	}

	vector<vector<int>> get_result() {
		/*
		TODO: Gasiti componentele tare conexe ale grafului orientat cu
		n noduri, stocat in adj. Rezultatul se va returna sub forma
		unui vector, ale carui elemente sunt componentele tare conexe
		detectate. Nodurile si componentele tare conexe pot fi puse in orice
		ordine in vector.

		Atentie: graful transpus este stocat in adjt.
		*/
		vector<vector<int>> sol;
		kosaraju();
		sol = scc;
		return sol;
	}

	void kosaraju() {
		// Indexing from 1;
		topsort.push_back(-1);

		// Traverse the initial graph
		for (int i = 1; i <= n; ++i) {
			if (!visited[i]) {
				dfs(i);
			}
		}

		// Traverse the transposed graph generated by
		// the topological sort
		for (int i = n; i >= 1; --i) {
			if (visited[topsort[i]]) { // not visited on the adj_t list
				// Build a new scc
				vector<int> current_scc;
				dfs_t(topsort[i], current_scc);
				scc.push_back(current_scc);
			}
		}
	}

	// DFS on the normal graph
	void dfs(int node) {
		visited[node] = 1;

		for (auto &ngh : adj[node]) {
			if (!visited[ngh]) {
				dfs(ngh);
			}
		}

		// Add node to topsort
		topsort.push_back(node);
	}

	// DFS on the transposed graph
	void dfs_t(int node, vector<int> &current_scc) {
		visited[node] = 0;
		current_scc.push_back(node);

		for (auto &ngh : adj_trans[node]) {
			if (visited[ngh]) {
				dfs_t(ngh, current_scc);
			}
		}
	}

	void print_output(const vector<vector<int>>& result) {
		ofstream fout("ctc.out");
		fout << result.size() << '\n';
		for (const auto& ctc : result) {
			for (int nod : ctc) {
				fout << nod << ' ';
			}
			fout << '\n';
		}
		fout.close();
	}
};

// Please always keep this simple main function!
int main() {
	// Allocate a Task object on heap in order to be able to
	// declare huge static-allocated data structures inside the class.
	Task *task = new Task();
	task->solve();
	delete task;
	return 0;
}