UVa :: 11709 :: Trust groups

Problem : Please find the problem here.

Explanation : Find the number of strongly connected components.  This can be done using Kosaraju's algorithm or Tarjan's Algorithm. I used the first one. Basically just do topological sort on the graph and then count the connected components with the DFS or BFS.

Code : Used Kosaraju's Algorithm.

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

const int mxN = 1e3;
int n, m;
string in;
map<string, int> node_id;
vector<int> adj[mxN], adjr[mxN], ts;
bool vis[mxN];

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

void dfs2(int u){
    vis[u] = 1;
    for(int v : adjr[u]){
	if(!vis[v]){
	    dfs2(v);
	}
    }
}

// Kosaraju's Algorithm

int SCC_count(){
	
    for(int i = 0; i < n; i++){
	if(!vis[i]){
	    dfs1(i);
	}
    }
    reverse(ts.begin(), ts.end());
    memset(vis, false, sizeof(vis));
    int cnt = 0;
    for(int i = 0; i < n; i++){
        if(!vis[ts[i]]){
	    dfs2(ts[i]), cnt++;
	}
    }
    return cnt;
}

void init(){
    memset(vis, false, sizeof(vis));
    ts.clear();
    node_id.clear();
    for(int i = 0; i < n; i++){
        adj[i].clear();
	adjr[i].clear();
    }
}

int main()
{
    while(cin >> n >> m && (n || m)){
        init();
	cin.ignore();
	int id = 0;
	for(int i = 0; i < n; i++){
	    getline(cin, in);
	    if(node_id.find(in) == node_id.end()){
		node_id[in] = id++;
	    }
	}
	for(int i = 0, u, v; i < m; i++){
	    getline(cin, in);
	    u = node_id[in];
	    getline(cin, in);
	    v = node_id[in];
	    adj[u].emplace_back(v);
	    adjr[v].emplace_back(u);
        }
	cout << SCC_count() << '\n';
    }	
    return 0;
}

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;
}