Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <vector>
- #include <map>
- using namespace std;
- #define forn(i, n) for(int i = 0; i < (int) (n); i++)
- #define isIn(i, c) ((c).find(i) != (c).end())
- const int SIZE = 110000;
- map< pair<int, int>, int > ps;
- vector<int> edges[SIZE];
- vector<bool> visited(SIZE);
- int N, M;
- void dfs(int s){
- if(!visited[s]){
- visited[s] = true;
- forn(i, edges[s].size()) dfs(edges[s][i]);
- }
- }
- int main(){
- #ifdef ACM
- freopen("test.in", "r", stdin);
- #endif
- while(scanf("%d", &M) && M != -1){
- N = 0;
- ps.clear();
- forn(i, M){
- int x1, x2, y1, y2;
- scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
- pair<int, int> p1(x1, y1), p2(x2, y2);
- if(!isIn(p1, ps)){
- edges[N].clear();
- ps.insert(make_pair(p1, N++));
- }
- if(!isIn(p2, ps)){
- edges[N].clear();
- ps.insert(make_pair(p2, N++));
- }
- edges[ ps[p1] ].push_back(ps[p2]);
- edges[ ps[p2] ].push_back(ps[p1]);
- }
- fill(visited.begin(), visited.end(), false);
- int C = 0;
- forn(i, N){
- if(!visited[i]) C++;
- dfs(i);
- }
- printf("%d\n", C + M - N);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment