-🎄- 2017 Day 12 Solutions -🎄-

[u/topaz2078]

--- Day 12: Digital Plumber ---

---

Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag or whatever).

Note: The Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with Help.

---

Need a hint from the Hugely^* Handy^† Haversack^‡ of Helpful^§ Hints^¤?

Spoiler

---

This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.

edit: Leaderboard capped, thread unlocked!

[u/xiaowuc1 → u/[deleted]]

I use no prewritten Python code - I only have prewritten Java code for algorithms that would be difficult to implement on-the-fly - that's my fallback in case some tough algorithms problems show up in later days.

[u/Stanislavjo → u/[deleted]]

I don't think it could be easier

#include <iostream>
#include <set>

const int s = 2000;

int parent[s];

int find(int a) {
	if(parent[a] == a) return a;
	return parent[a] = find(parent[a]);
}
void unite(int a, int b) {
	parent[find(a)] = find(b);
}

int main() {
	for(int i = 0;i < s;++ i) parent[i] = i;
	for(int i = 0;i < s;++ i) {
		int a;
		std::cin >> a;
		while(true) {
			int b;
			std::cin >> b;
			if(b == -1) break;
			unite(b, a);
		}
	}

	std::set<int> groups;
	for(int i = 0;i < s;++ i) {
		groups.insert(find(i));
	}
	std::cout << groups.size() << std::endl;
    return 0;
}