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

484 – The Department of Redundancy Department

Count and print. C++ code:

#include <cstdio>
#include <vector>
#include <map>
using namespace std;

typedef long long int64;

map<int64, int64> nInput;
vector<int64> input;
int64 n;

int main() {
	// input
	while (scanf("%lld", &n) == 1) {
		if (!nInput[n])
			input.push_back(n);
		nInput[n]++;
	}
	// output
	for (unsigned int i = 0; i < input.size(); ++i)
		printf("%lld %lld\n", input[i], nInput[input[i]]);
	return 0;
}

10226 – Hardwood Species

A simple sorting and counting problem.

#include <string>
#include <cstdio>
#include <map>
using namespace std;

map<string, long long> nTree;
int nCase, nTreeTot;
char line[64];

int main() {
	gets(line);
	sscanf(line, "%d", &nCase);
	gets(line);
	for (int caseI = 0; caseI < nCase; ++caseI) {
		// init
		if (caseI)
			printf("\n");
		nTreeTot = 0;
		nTree.clear();
		// input & slove
		for (string t; gets(line) && line[0]; ++nTree[t], ++nTreeTot)
			t = string(line);
		// print
		for (map<string, long long>::iterator it = nTree.begin(); it != nTree.end(); ++it)
			printf("%s %.4lf\n", it->first.c_str(), 100.0 * it->second / nTreeTot);
	}
	return 0;
}

10260 – Soundex

A simple ad-hoc problem. C++ implementation:

#include <cstdio>
#include <map>
using namespace std;

map<char, char> m;
char in[32], out[32], prev;
int outI;

int main() {
	m['B'] = m['F'] = m['P'] = m['V'] = '1';
	m['C'] = m['G'] = m['J'] = m['K'] = m['Q'] = m['S'] = m['X'] = m['Z'] = '2';
	m['D'] = m['T'] = '3';
	m['L'] = '4';
	m['M'] = m['N'] = '5';
	m['R'] = '6';
	while (scanf("%s", in) == 1) {
		outI = 0;
		prev = '7';
		for (int i = 0; in[i]; ++i)
			if (m.find(in[i]) != m.end()) {
				if (m[in[i]] != prev)
					prev = out[outI++] = m[in[i]];
				prev = m[in[i]];
			} else
				prev = in[i];
		out[outI] = '\0';
		printf("%s\n", out);
	}
	return 0;
}

11888 – Abnormal 89’s

C++ brute-force rank 88 solution:

#include <cstdio>
#include <cstring>
using namespace std;

bool isPalindrome(char* s, int n) {
	for (int i = n / 2; i > -1; --i)
		if (s[i] != s[n - i - 1])
			return false;
	return true;
}

bool isAlindrome(char* s, int n) {
	for (int i = 1; i < n; ++i)
		if (isPalindrome(s, i) && isPalindrome(s + i, n - i))
			return true;
	return false;
}

int main() {
	int nCase, n;
	scanf("%d", &nCase);
	char* line = new char[200000];
	while (nCase--) {
		scanf("%s", line);
		n = strlen(line);
		if (isAlindrome(line, n))
			printf("alindrome\n");
		else if (isPalindrome(line, n))
			printf("palindrome\n");
		else
			printf("simple\n");
	}
	return 0;
}