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

10305 – Ordering Tasks

Given a set of dependent tasks, find the order in which these tasks have to be executed.

The solution is found via a topological sort.

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

vector<map<int, int> > graph;
vector<int> sortedNodes;

void topSort() {
	sortedNodes.clear();
	vector<int> inDegree = vector<int>(graph.size(), 0);
	for (size_t i = 0; i < graph.size(); ++i)
		for (map<int, int>::iterator itr = graph[i].begin(); itr != graph[i].end(); ++itr)
			++inDegree[itr->first];
	queue<int> q;
	for (size_t i = 0; i < graph.size(); ++i)
		if (inDegree[i] == 0)
			q.push(i);
	while (q.size()) {
		int p = q.front();
		sortedNodes.push_back(p), q.pop();
		for (map<int, int>::iterator itr = graph[p].begin(); itr != graph[p].end(); ++itr)
			if (!(--inDegree[itr->first]))
				q.push(itr->first);
	}
}

int main() {
	int n, m;
	while (cin >> n >> m && (n || m)) {
		// input
		graph.clear();
		for (int i = 0; i < n; ++i)
			graph.push_back(map<int, int>());
		for (int i = 0, x, y; i < m; ++i)
			cin >> x >> y, --x, --y, graph[x][y] = 1;
		// solve
		topSort();
		cout << (sortedNodes[0] + 1);
		for (int i = 1; i < n; ++i)
			cout << " " << (sortedNodes[i] + 1);
		cout << endl;
	}
	return 0;
}

11516 – WiFi

Given a street (a straigt line), a set of houses (points on that line) and a number of wireless access points (not placed yet), find the minimum range required for the access points to cover all the houses.

A binary search solution:

• Given the houses’ positions and the ranges, we can find the required number of access points n'. It’s correct to calculate this using some greedy algorithm.
• If n' < n (we have extra access points), decrease the range. Otherwise, increase the range.

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
using namespace std;

const double eps = 10E-4;
vector<int> house;

int nPointReq(double d) {
	int n = 1;
	double covered = house[0] + d;
	for (size_t i = 0; i < house.size(); ++i)
		if (house[i] > covered)
			covered = house[i] + d, ++n;
	return n;
}

int main() {
	int nCase, nPoint, nHouse;
	cin >> nCase;
	cout.precision(1);
	while (nCase--) {
		// input
		cin >> nPoint >> nHouse;
		house.clear();
		for (int i = 0, d; i < nHouse; ++i)
			cin >> d, house.push_back(d);
		sort(house.begin(), house.end());
		// solve
		double lD = 0, mD, hD = house[house.size() - 1];
		do {
			mD = (hD + lD) / 2.0;
			if (nPointReq(mD) > nPoint)
				lD = mD;
			else
				hD = mD;
		} while (hD - lD > eps);
		cout << fixed << (round(mD * 10) / 20.0) << endl;
	}
	return 0;
}

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