tcbpg

Untitled

Aug 25th, 2011
78
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.13 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <map>
  5.  
  6. using namespace std;
  7.  
  8. #define forn(i, n) for(int i = 0; i < (int) (n); i++)
  9. #define isIn(i, c) ((c).find(i) != (c).end())
  10.  
  11. const int SIZE = 110000;
  12.  
  13. map< pair<int, int>, int > ps;
  14.  
  15. vector<int> edges[SIZE];
  16. vector<bool> visited(SIZE);
  17.  
  18. int N, M;
  19.  
  20. void dfs(int s){
  21.     if(!visited[s]){
  22.         visited[s] = true;
  23.         forn(i, edges[s].size()) dfs(edges[s][i]);
  24.     }
  25. }
  26.  
  27. int main(){
  28. #ifdef ACM
  29.     freopen("test.in", "r", stdin);
  30. #endif
  31.  
  32.     while(scanf("%d", &M) && M != -1){
  33.         N = 0;
  34.         ps.clear();
  35.  
  36.         forn(i, M){
  37.             int x1, x2, y1, y2;
  38.             scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
  39.  
  40.             pair<int, int> p1(x1, y1), p2(x2, y2);
  41.  
  42.             if(!isIn(p1, ps)){
  43.                 edges[N].clear();
  44.                 ps.insert(make_pair(p1, N++));
  45.             }
  46.  
  47.             if(!isIn(p2, ps)){
  48.                 edges[N].clear();
  49.                 ps.insert(make_pair(p2, N++));
  50.             }
  51.  
  52.             edges[ ps[p1] ].push_back(ps[p2]);
  53.             edges[ ps[p2] ].push_back(ps[p1]);
  54.         }
  55.  
  56.         fill(visited.begin(), visited.end(), false);
  57.         int C = 0;
  58.  
  59.         forn(i, N){
  60.             if(!visited[i]) C++;
  61.             dfs(i);
  62.         }
  63.  
  64.         printf("%d\n", C + M - N);
  65.     }
  66.  
  67.     return 0;
  68. }
Advertisement
Add Comment
Please, Sign In to add comment