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 : 558 :: Wormholes

Problem : Please find the problem here.

Explanation : The problem basically asks for the negative cycle in the given directed graph.

Code : Used Bellman-Ford Algorithm .

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

const int mxN = 2e3;
int n, m, d[mxN], p[mxN];
vector<array<int, 2>> adj[mxN];
bool vis[mxN];

bool bellman_ford(int src){
    d[src] = 0;

    p[src] = -1;
    vis[src] = 1;

    for(int i = 0; i < n; i++){

        for(int u = 0; u < n; u++){
	    for(int k = 0; k < (int)adj[u].size(); k++){

                array<int, 2> vv = adj[u][k];

                int v = vv[1];
		int cost = vv[0];
		if(vis[u]){
		    if(!vis[v] || ((d[u]+cost) < d[v])){
		        if(i < n-1){
			    vis[v] = 1;
			    d[v] = d[u]+cost;
		            p[v] = u;
			}
			else{

                            return true;
			}
		    }
	        }
	    }
        }
    }
    return false;
}

void init(){
    for(int i = 0; i < n; i++){
        adj[i].clear();
    }
    memset(vis, false, sizeof(vis));
    memset(p, -1, sizeof(p));
    memset(d, -1, sizeof(d));
}

int main()
{

    ofstream fout("out");
    int t;
    cin >> t;
    while(t--){

        cin >> n >> m;
	init();
	for(int i = 0, a, b, c; i < m; i++){
	    cin >> a >> b >> c;
	    adj[a].push_back({c, b});
	    //adj[b].push_back({c, a});
	}
	bool ok = bellman_ford(0);
	cout << (ok?"possible":"not possible") << '\n';
    }	
    return 0;
}

UVa : 10765 :: Doves and Bombs

Problem : Please find the problem here.

Summary and Explanation : The problem asked to find the vertices with the maximum number of childrens. These vertices mostly (not entirely) are the Articulation points. Since we need to print m such vertices, if we run out of Articulation points in the graph then we can just print the ordinary vertices with maximum number of childs.
This problem is so general that I dont want to use the term articulation points, because we just need to print the nodes with maximum number of childrens with their node index in the order asked in the problem.

Code : Used DFS. Stored the number of childrens for each vertex. Notice at the end of DFS, the If condition is for cycles in the graph. In case of a cycle strating from the given node, the number of childrens for that node should be decreased by 1.

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

const int mxN = 1e4;
int n, m, u, v, timer, tin[mxN], low[mxN], c[mxN];
vector<int> adj[mxN];
array<int, 2> ans[mxN]; // index 0 strores the vertex no. | index 1 stores the number of childrens of the vertex;
bool vis[mxN];

bool cmp(array<int, 2> a, array<int, 2> b){
    if(a[1] != b[1]){
        return a[1] > b[1];
    }
    else{
        return a[0] < b[0];
    }
}

void dfs(int u, int pu = -1){
    vis[u] = 1;
    tin[u] = low[u] = timer++;
    int children = 0;
    for(int v : adj[u]){
        if(v == u) continue;
        if(vis[v]){
            low[u] = min(low[u], tin[v]);
        }
        else{
            dfs(v, u);
            low[u] = min(low[u], low[v]);
            if(low[v] >= tin[u] && pu != -1){
                ans[u][1]++;
            }
            c[u]++;
            children++;
        }
    }
    if(pu == -1 && children > 1){
        ans[u][1] = children-1;
    } 
}

void init(){
    memset(vis, false, sizeof(vis));
    memset(tin, 0, sizeof(tin));
    memset(low, 0, sizeof(low));
    memset(c, 0, sizeof(c));
    timer = 0;
    for(int i = 0; i < n; i++){
        adj[i].clear();
        ans[i][0] = i;
        ans[i][1] = 0;
    }
}

int main()
{
    ofstream fout("out");
    while(scanf("%d %d", &n, &m) && (n&&m)){
        init();
        while(scanf("%d %d", &u, &v) && !(u == -1 || v == -1)){
            adj[u].emplace_back(v);
            adj[v].emplace_back(u);
        }
        for(int i = 0; i < n; i++){
            if(!vis[i]){
                dfs(i);
            }
        }
        sort(ans, ans+n, cmp);
        for(int i = 0; i < m; i++){
            cout << ans[i][0] << ' ' << ans[i][1]+1 << '\n';

        }
        cout << '\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;
}