HDU 5348 MZL's endless loop

  1 #include<iostream>
  2 #include<stdio.h>
  3 #include<algorithm>
  4 #include<math.h>
  5 #include<set>
  6 #include<vector>
  7 #include<string.h>
  8 #include<string>
  9 #include<map>
 10 #include<bitset>
 11 
 12 #define inf 2011111111
 13 #define N 423456
 14 using namespace std;
 15 
 16 struct node
 17 {
 18     int u,v;
 19 }e[N*2];
 20 
 21 int head[N],pre[N*2],Next[N*2],deg[N],ans[N];
 22 int n,m,tot;
 23 
 24 void init()
 25 {
 26   memset(head,-1,sizeof(head));
 27   memset(Next,-1,sizeof(Next));
 28   memset(deg,0,sizeof(deg));
 29   tot=0;
 30 }
 31 
 32 void add(int u,int v)
 33 {
 34   e[tot].u=u;
 35   e[tot].v=v;
 36   pre[tot]=head[u];
 37   head[u]=tot++;
 38 
 39   e[tot].u=v;e[tot].v=u;
 40   pre[tot]=head[v];
 41   head[v]=tot++;
 42 }
 43 //每次从一个奇度点中遍历的结论;
 44 //奇数点的个数一定是偶数，每次从奇数点的度开始遍历，那么每次一定可以消去两个奇数点，最后的最后一定都是度为偶数的点，满足欧拉性质，就遍历一边了
 45 // 遍历时要 删边
 46 
 47 void dfs(int u)//手写栈
 48 {
 49   while (head[u]!=-1)
 50   {
 51     deg[u]--;
 52     int i=head[u];
 53     int v=e[i].v;
 54     if (i&1) ans[(i>>1)+1]=0;
 55     else ans[(i>>1)+1]=1;
 56 
 57     int pp,nn;
 58     if (head[u]==i) head[u]=pre[i];
 59 
 60     //在临界表中 把边删除，就是把一条边的左右 边，pre,next，互相指，等于把这条边删除了，每条边作两次。
 61     pp=pre[i];
 62     nn=Next[i];
 63     if (pp!=-1) Next[pp]=nn;
 64     if (nn!=-1) pre[nn]=pp;
 65 
 66     int _i=i^1;
 67 
 68     if (head[v]==_i) head[v]=pre[_i];
 69 
 70     pp=pre[_i];
 71     nn=Next[_i];
 72     if (pp!=-1) Next[pp]=nn;
 73     if (nn!=-1) pre[nn]=pp;
 74     u=v;
 75     if (deg[v]) deg[v]--;
 76   }
 77 }
 78 
 79 
 80 int main()
 81 {
 82   int T;
 83   scanf("%d",&T);
 84   while (T--)
 85   {
 86      init();
 87      scanf("%d%d",&n,&m);
 88      for (int i=1;i<=m;i++)
 89      {
 90         int u,v;
 91         scanf("%d%d",&u,&v);
 92         add(u,v);
 93         deg[u]++;
 94         deg[v]++;
 95      }
 96      for (int i=0;i<tot;i++)
 97      if (pre[i]!=-1) Next[pre[i]]=i;
 98 
 99      for (int i=1;i<=n;i++)
100      Next[head[i]]=-1;
101 
102      for (int i=1;i<=n;i++)
103      if (deg[i]&1) dfs(i);
104      for (int i=1;i<=n;i++)
105      if (deg[i]) dfs(i);
106 
107      for (int i=1;i<=m;i++) printf("%d
",ans[i]);
108   }
109   return 0;
110 }

View Code

copy过来的，主要是手动删除边实在是麻烦，还要记入每条边的前驱后继，再手动栈，着实GG

SET，很好用虽然多一点复杂度，但是过这题还可以，

思路都差不多，都是从一个奇度的点开始遍历，然后在处理，不断删除边。由于在SET里面还是好删边的

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<algorithm>
 4 #include<math.h>
 5 #include<set>
 6 #include<vector>
 7 #include<string.h>
 8 #include<string>
 9 #include<map>
10 #include<bitset>
11 
12 #define inf 2011111111
13 #define N 303456
14 #define mp make_pair
15 using namespace std;
16 
17 int ans[N];
18 set<pair<int,int> >S[N];
19 set<pair<int,int> >::iterator it;
20 int deg[N];
21 pair<int,int> tmp;
22 
23 
24 void dfs(int u)
25 {
26     while (S[u].size())
27     {
28         it=S[u].begin();
29         deg[u]--;
30         int xx=it->second;
31         if (xx%2==0)
32         ans[xx/2+1]=1;
33         else ans[xx/2+1]=0;
34 
35         int v=it->first;
36         tmp={u,xx^1};
37         S[u].erase(it);
38         if (S[v].find(tmp)!=S[v].end())
39         S[v].erase(tmp);
40         deg[v]--;
41         u=v;
42   }
43 }
44 
45 int main()
46 {
47   int T;
48   scanf("%d",&T);
49   int n,m;
50   while (T--)
51   {
52      scanf("%d%d",&n,&m);
53      for (int i=0;i<=n;i++) S[i].clear(),deg[i]=0;
54 
55      for (int i=1;i<=m;i++)
56      {
57         int u,v;
58         scanf("%d%d",&u,&v);
59         S[u].insert({v,(i-1)*2});
60         S[v].insert({u,i*2-1});
61         deg[u]++;
62         deg[v]++;
63      }
64 
65      for (int i=1;i<=n;i++)
66      if (deg[i]&1) dfs(i);
67      for (int i=1;i<=n;i++)
68      if (deg[i]) dfs(i);
69 
70      for (int i=1;i<=m;i++) printf("%d
",ans[i]);
71   }
72   return 0;
73 }