UVa : 11504 :: Dominos Solution

Problem : Please find the problem here.

Summary : The given graph can be stored as the directed graph. so that for any SCC(strongly connected component) if we push any of the domino in it, eventually all the dominos will fall in that SCC. So it really doesnt matter which domino we choose in the component, what matters is the order of the connected components we choose. For instance there can be possible case where a SCC can be use to push another SCC but the reverse is not true, so we want to push all these SCC's first which can push another SCC's.

We can first do a topological sort on the vertices and then we can count the number of SCC'c in the graph in the usual manner using dfs.

Code :

#include <bits/stdc++.h>
using namespace std;


const int mxN = 1e5+5;
int n, m;
vector<int> adj[mxN], ts;
bool vis[mxN];


void dfs(int u){
	vis[u] = 1;
	for(int v : adj[u]){
		if(!vis[v]){
			dfs(v);
		}
	}
	ts.push_back(u);
}
int main()
{

	int t;
	cin >> t;
	while(t--){
		cin >> n >> m;
		for(int i = 0; i <= n; i++){
			adj[i].clear();
		}
		ts.clear();
		for(int i = 0, u, v; i < m; i++){
			cin >> u >> v;
			adj[u].push_back(v);
		}
		memset(vis, 0, sizeof(vis));
		for(int i = 1; i <= n; i++){
			if(!vis[i]){
				dfs(i);
			}
		}
		memset(vis, false, sizeof(vis));
		reverse(ts.begin(), ts.end());
		int cnt = 0;
		for(int i = 0; i < n; i++){
			int u = ts[i];
			if(!vis[u]){
				dfs(u); cnt++;
			}
		}
		cout << cnt << '\n';
	}
	return 0;
}