315 – Network

Problem Statement

Given a connected undirected graph, find its critical nodes (articulation points). A critical node is a node which its removal leaves the graph disconnected.

A straight-forward solution –to remove each node and do a DFS check for connectivity– will get an AC, but this is an implementation that uses Tarjan’s DFS algorithm for finding Articulation Point:

#include <algorithm>
#include <iostream>
#include <fstream>
#include <cstring>
#include <limits>
#include <sstream>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <set>
using namespace std;

set<int> apNodes, apVis;
set<pair<int, int> > apEdges;
void articulationPointAndBridge(map<int, map<int, int> > &graph, int s) {
//     cout << "ARTICULATION POINT AND BRIDGE" << endl;
    map<int, int> parent, num_dfs, num_low;
    int children_s = 0, num_dfs_size = 0;
    stack<int> stk;
    parent[s] = s, stk.push(s);
    // dfs
    while (stk.size()) {
        int u = stk.top();
        // grey
        if (apVis.find(u) == apVis.end()) {
            num_dfs[u] = num_low[u] = num_dfs_size++;
            apVis.insert(u);
            children_s += u != s && parent[u] == s;
            for (map<int, int>::reverse_iterator v = graph[u].rbegin();
                 v != graph[u].rend(); ++v)
                // grey to white
                if (apVis.find(v->first) == apVis.end())
                    parent[v->first] = u, stk.push(v->first);
                // grey to grey
                else if (parent[u] != v->first)
                    num_low[u] = min(num_low[u], num_dfs[v->first]);
        }
        // black
        else {
            if (parent[u] != u) {
                // POINTS
                if (num_dfs[parent[u]] <= num_low[u])
                    apNodes.insert(parent[u]);
                // BRIDGES
                if (num_dfs[parent[u]] < num_low[u])
                    if (u < parent[u])
                        apEdges.insert(make_pair(u, parent[u]));
                    else
                        apEdges.insert(make_pair(parent[u], u));
                num_low[parent[u]] = min(num_low[parent[u]], num_low[u]);
            }
            stk.pop();
        }
    }
    apNodes.erase(s);
    if (children_s > 1)
        apNodes.insert(s);
}

int main() {
    int n;
    string line;
    while (cin >> n && n) {
        // input
        getline(cin, line);
        bool inputDone = false;
        map<int, map<int, int> > graph;
        while (!inputDone) {
            getline(cin, line);
            stringstream ss(line);
            int u, v;
            ss >> u;
            if (!u)
                inputDone = true;
            while (ss >> v)
                graph[u][v] = 1, graph[v][u] = 1;
        }
        // solve
        apVis.clear(), apNodes.clear(), apEdges.clear();
        articulationPointAndBridge(graph, graph.begin()->first);
        cout << apNodes.size() << endl;
    }
}

796 – Critical Links

Problem Statement

Given an undirected graph, find its critical edges. A critical edge is one that when removed disconnects any two connected nodes.

The brute-force solution –removing an edge and checking for connectivity– will work. But this is an implementation using Tarjan’s DFS Bridge finding algorithm.

set<int> apNodes, apVis;
set<pair<int, int> > apEdges;
void articulationPointAndBridge(map<int, map<int, int> > &graph, int s) {
    map<int, int> parent, num_dfs, num_low;
    int children_s = 0, num_dfs_size = 0;
    stack<int> stk;
    parent[s] = s, stk.push(s);
    // dfs
    while (stk.size()) {
        int u = stk.top();
        // grey
        if (apVis.find(u) == apVis.end()) {
            num_dfs[u] = num_low[u] = num_dfs_size++;
            apVis.insert(u);
            children_s += u != s && parent[u] == s;
            for (map<int, int>::reverse_iterator v = graph[u].rbegin();
                 v != graph[u].rend(); ++v)
                // grey to white
                if (apVis.find(v->first) == apVis.end())
                    parent[v->first] = u, stk.push(v->first);
                // grey to grey
                else if (parent[u] != v->first)
                    num_low[u] = min(num_low[u], num_dfs[v->first]);
        }
        // black
        else {
            if (parent[u] != u) {
                // POINTS
                if (num_dfs[parent[u]] <= num_low[u])
                    apNodes.insert(parent[u]);
                // BRIDGES
                if (num_dfs[parent[u]] < num_low[u])
                    if (u < parent[u])
                        apEdges.insert(make_pair(u, parent[u]));
                    else
                        apEdges.insert(make_pair(parent[u], u));
                num_low[parent[u]] = min(num_low[parent[u]], num_low[u]);
            }
            stk.pop();
        }
    }
    apNodes.erase(s);
    if (children_s > 1)
        apNodes.insert(s);
}

int main() {
    string str;
    int n, a, b, m;
    while (cin >> n) {
        // input
        map<int, map<int, int> > graph;
        for (int i = 0; i < n; ++i) {
            cin >> a;
            cin >> str;
            stringstream ss(str.substr(1, str.length() - 2));
            ss >> m;
            for (int j = 0; j < m; ++j)
                cin >> b, graph[a][b] = graph[b][a] = 1;
        }
        // solve
        apVis.clear(), apEdges.clear(), apNodes.clear();
        for (map<int, map<int, int> >::iterator i = graph.begin();
             i != graph.end(); ++i)
            if (apVis.find(i->first) == apVis.end())
                articulationPointAndBridge(graph, i->first);
        // print
        cout << apEdges.size() << " critical links";
        for (set<pair<int, int> >::iterator i = apEdges.begin();
             i != apEdges.end(); ++i)
            cout << endl << i->first << " - " << i->second;
        cout << endl << endl;
    }
}

10986 – Sending email

Given a network of servers and the connections between them with their latency, find the fastest path for sending a message.

A straight-forward path finding problem. Dijkstra will do and Bellman Ford will get TLE.

#include <algorithm>
#include <iostream>
#include <limits>
#include <vector>
#include <queue>
#include <map>
using namespace std;

vector<map<int, int> > graph;

vector<int> dijkstraD, dijkstraP;
void dijkstra(int s) {
	dijkstraD = vector<int>(graph.size(), numeric_limits<int>::max());
	dijkstraP = vector<int>(graph.size(), -1);
	priority_queue<pair<int, int> > q;
	dijkstraP[s] = -s - 1;
	dijkstraD[s] = 0;
	q.push(make_pair(dijkstraD[s], s));
	while (!q.empty()) {
		pair<int, int> p = q.top();
		q.pop();
		if (dijkstraP[p.second] < 0) {
			dijkstraP[p.second] = -dijkstraP[p.second] - 1;
			for (map<int, int>::iterator itr = graph[p.second].begin();
				itr != graph[p.second].end(); ++itr)
				if (dijkstraP[itr->first] < 0
				&& dijkstraD[p.second] + graph[p.second][itr->first] < dijkstraD[itr->first]) {
					dijkstraP[itr->first] = -p.second - 1;
					dijkstraD[itr->first] = dijkstraD[p.second] + graph[p.second][itr->first];
					q.push(pair<int, int>(-dijkstraD[itr->first], itr->first));
				}
		}
	}
}

int main() {
	int N, n, m, s, t;
	cin >> N;
	for (int caseI = 0; caseI < N; ++caseI) {
		// input
		cin >> n >> m >> s >> t;
		graph.clear();
		for (int i = 0; i < n; ++i)
			graph.push_back(map<int, int>());
		for (int i = 0, a, b, w; i < m; ++i)
			cin >> a >> b >> w, graph[a][b] = graph[b][a] = w;
		// solve
		dijkstra(s);
		cout << "Case #" << (caseI + 1) << ": ";
		if (dijkstraD[t] == numeric_limits<int>::max())
			cout << "unreachable";
		else
			cout << dijkstraD[t];
		cout << endl;
	}
	return 0;
}

259 – Software Allocation

You’re given 10 computers and a set of programs that need to be executed. A computer cannot multitask. Each problem needs to run on a computer of a specific set. Find an assignment of the programs to the computers.

We map the problem to a graph and solve via maximum flow.
We have two layers of nodes; those of the computers and those of the programs. Each computer node is connected to a program node if and only if it can run the program. The source node is connected to all 10 computer nodes and all program nodes are connected to the sink node.
We run Edmond-Karp algorithm and if the maximum flow is less that the number of programs, we can’t find a satisfactory allocation. Otherwise, an allocation is found and can be retrieved by examining the graph.
C++ implementaion with rank 217:

#include <algorithm>
#include <cstring>
#include <cstdio>
#include <limits>
#include <queue>
using namespace std;

#define N 39
int cap[N][N], parent[N], s = 37, t = 38;

bool bfs() {
	queue<int> q;
	q.push(s);
	memset(parent, -1, sizeof parent);
	parent[s] = s;
	while (q.size()) {
		int u = q.front();
		q.pop();
		if (u == t)
			return true;
		for (int v = 0; v < N; ++v)
			if (parent[v] == -1 && cap[u][v] > 0)
				parent[v] = u, q.push(v);
	}
	return false;
}

int maxFlow() {
	int mf = 0, f, v;
	while (bfs()) {
		// min
		v = t;
		f = numeric_limits<int>::max();
		while (parent[v] != v)
			f = min(f, cap[parent[v]][v]), v = parent[v];
		// update
		v = t;
		mf += f;
		while (parent[v] != v)
			cap[parent[v]][v] -= f, cap[v][parent[v]] += f, v = parent[v];
	}
	return mf;
}

int main() {
	char line[1024], *c, nProg = 1, mf;
	while (true) {
		// init
		memset(cap, 0, sizeof cap);
		for (int i = 0; i < 10; ++i)
			cap[i][t] = 1;
		// input
		nProg = 0;
		while (gets(line) && line[0]) {
			nProg += (cap[s][line[0] - 'A' + 10] = line[1] - '0');
			c = &line[3];
			while (*c != ';')
				cap[line[0] - 'A' + 10][*c - '0'] = 1, ++c;
		}
		// output
		if (!nProg)
			break;
		mf = maxFlow();
		if (mf == nProg)
			for (int i = 0; i < 10; ++i) {
				int j;
				for (j = 0; j < 26; ++j)
					if (cap[i][j + 10])
						break;
				printf("%c", j == 26 ? '_' : j + 'A');
			}
		else
			printf("!");
		printf("\n");
	}
	return 0;
}

10801 – Lift Hopping

Given a 100-floor building with a number of elevators that are only allowed to stop at certain floors, find the fastest way to reach a given floor.

We can map the building to a graph. A floor is a node and any two floors that are connected by an elevator are two ends of an edge.Find the shortest path and you’re done. Beware that the graph is bidirectional.

#include <algorithm>
#include <limits>
#include <cstdio>
#include <cstring>
#include <queue>
#include <map>
using namespace std;

vector<map<int, int> > graph;
vector<int> dijkstraD, dijkstraP;

void dijkstra(int s) {
	dijkstraD = vector<int>(graph.size(), numeric_limits<int>::max());
	dijkstraP = vector<int>(graph.size(), -1);
	priority_queue<pair<int, int> > q;
	dijkstraP[s] = -s - 1;
	dijkstraD[s] = 0;
	q.push(make_pair(dijkstraD[s], s));
	while (!q.empty()) {
		pair<int, int> p = q.top();
		q.pop();
		if (dijkstraP[p.second] < 0) {
			dijkstraP[p.second] = -dijkstraP[p.second] - 1;
			for (map<int, int>::iterator itr = graph[p.second].begin();
			itr != graph[p.second].end(); ++itr)
				if (dijkstraP[itr->first] < 0
				&& dijkstraD[p.second] + graph[p.second][itr->first] < dijkstraD[itr->first]) {
					dijkstraP[itr->first] = -p.second - 1;
					dijkstraD[itr->first] = dijkstraD[p.second] + graph[p.second][itr->first];
					q.push(pair<int, int>(-dijkstraD[itr->first], itr->first));
				}
		}
	}
}

int main() {
	int n, k, t[8], K = 100;
	char line[1024], *p;
	while (scanf("%d %d", &n, &k) == 2) {
		// build graph
		graph.clear();
		// nodes
		for (int i = n * K; i > -1; --i)
			graph.push_back(map<int, int>());
		// elevator speed
		for (int i = 0; i < n; ++i)
			scanf("%d", &t[i]);
		// changing elevators cost
		for (int i = 1; i < n; ++i)
			graph[K * (i - 1)][K * i] = graph[K * i][K * (i - 1)] = 0;
		for (int j = 1; j < K; ++j)
			for (int i = 0; i < n; ++i)
				for (int i2 = 0; i2 < n; ++i2)
					if (i != i2)
						graph[K * i + j][K * i2 + j] = 60;
		// elevator stop
		gets(line);
		for (int i = 0; i < n; ++i) {
			int prev, cur;
			gets(line);
			p = strtok(line, " ");
			sscanf(p, "%d", &prev);
			while ((p = strtok(NULL, " "))) {
				sscanf(p, "%d", &cur);
				graph[K * i + prev][K * i + cur] =
				graph[K * i + cur][K * i + prev] =
				t[i] * abs(cur - prev);
				prev = cur;
			}
		}
		//
		int d = numeric_limits<int>::max();
		dijkstra(0);
		for (int i = 0; i < n; ++i)
			d = min(d, dijkstraD[K * i + k]);
		if (d == numeric_limits<int>::max())
			printf("IMPOSSIBLE\n");
		else
			printf("%d\n", d);
	}
	return 0;
}