单向连通图 Going from u to v or from v to u? poj2762

  1 #include <cstdio>
  2 #include <cstdlib>
  3 #include <cmath>
  4 #include <cstring>
  5 #include <string>
  6 #include <algorithm>
  7 #include <iostream>
  8 using namespace std;
  9 #define ll long long
 10 
 11 const double eps=1e-8;
 12 const ll inf=1e9;
 13 const ll mod=1e9+7;
 14 const int maxn=1e3+10;
 15 
 16 struct node
 17 {
 18     int d;
 19     node *to;
 20 }*e[maxn];
 21 
 22 bool vis[maxn];
 23 
 24 int num,cnt_st,st[maxn],dfn[maxn],low[maxn],cnt_group,group[maxn],cnt_single,gx[maxn],gy[maxn];
 25 bool vis_st[maxn],ifok;
 26 
 27 void tarjan(int d)
 28 {
 29     dfn[d]=low[d]=++num;
 30     vis[d]=1;
 31     st[++cnt_st]=d;
 32     node *p=e[d];
 33     while (p)
 34     {
 35         if (!vis[p->d])
 36         {
 37             tarjan(p->d);
 38             low[d]=min(low[d],low[p->d]);
 39         }
 40         else if (!vis_st[p->d])
 41             low[d]=min(low[d],dfn[p->d]);
 42         p=p->to;
 43     }
 44     if (dfn[d]==low[d])
 45     {
 46         cnt_group++;
 47         while (d!=st[cnt_st])
 48         {
 49             group[st[cnt_st]]=cnt_group;
 50             vis_st[st[cnt_st]]=1;
 51             cnt_st--;
 52         }
 53         group[st[cnt_st]]=cnt_group;
 54         vis_st[st[cnt_st]]=1;
 55         cnt_st--;
 56     }
 57 }
 58 
 59 int main()
 60 {
 61     node *p;
 62     int T,n,m,x,y,i;
 63     scanf("%d",&T);
 64     while (T--)
 65     {
 66         scanf("%d%d",&n,&m);
 67         for (i=1;i<=n;i++)
 68             e[i]=NULL;
 69 
 70         while (m--)
 71         {
 72             scanf("%d%d",&x,&y);
 73             p=new node();
 74             p->d=y;
 75             p->to=e[x];
 76             e[x]=p;
 77         }
 78 
 79         memset(vis,0,sizeof(vis));
 80         memset(vis_st,0,sizeof(vis_st));
 81         num=0,cnt_st=0,cnt_group=0;
 82         for (i=1;i<=n;i++)
 83             if (!vis[i])
 84                 tarjan(i);
 85 
 86         /*
 87         if all are ok:需要的是链式结构
 88         1.对于一个子图，最多只有一个子图指向它，最多只有一个子图被它指向(非头结点)
 89         2.有且只有一个子图，没有子图指向它(头结点)
 90         */
 91 
 92         ifok=1,cnt_single=0;
 93         memset(gx,0,sizeof(gx));
 94         memset(gy,0,sizeof(gy));
 95         for (i=1;i<=n;i++)
 96         {
 97             p=e[i];
 98             while (p)
 99             {
100                 ///i -> p->d
101                 if (group[p->d]!=group[i])
102                 {
103                     if (gx[group[p->d]]==0)
104                         gx[group[p->d]]=group[i];
105                     else if (gx[group[p->d]]!=group[i])
106                         ifok=0;
107 
108                     if (gy[group[i]]==0)
109                         gy[group[i]]=group[p->d];
110                     else if (gy[group[i]]!=group[p->d])
111                         ifok=0;
112                 }
113                 p=p->to;
114             }
115         }
116         for (i=1;i<=cnt_group;i++)
117             if (!gx[i])
118                 cnt_single++;
119 
120         printf("%s
",(ifok&(cnt_single==1))?"Yes":"No");
121     }
122     return 0;
123 }
124 /*
125 10
126 3 2
127 1 2
128 3 2
129 
130 4 3
131 1 2
132 2 3
133 3 1
134 
135 3 3
136 1 2
137 2 3
138 3 1
139 
140 5 4
141 1 2
142 2 3
143 3 4
144 4 5
145 
146 3 2
147 1 2
148 1 3
149 
150 3 2
151 1 2
152 3 2
153 
154 4 3
155 1 2
156 2 3
157 3 1
158 
159 3 3
160 1 2
161 2 3
162 3 1
163 
164 5 4
165 1 2
166 2 3
167 3 4
168 4 5
169 
170 3 2
171 1 2
172 1 3
173 */

  1 #include <cstdio>
  2 #include <cstdlib>
  3 #include <cmath>
  4 #include <cstring>
  5 #include <string>
  6 #include <algorithm>
  7 #include <iostream>
  8 using namespace std;
  9 #define ll long long
 10 //#include <map>
 11 
 12 const double eps=1e-8;
 13 const ll inf=1e9;
 14 const ll mod=1e9+7;
 15 const int maxn=1e3+10;
 16 
 17 struct node
 18 {
 19     int d;
 20     node *to;
 21 }*e[maxn];
 22 
 23 bool vis[maxn],f[maxn][maxn];
 24 int c,q[maxn];
 25 
 26 //void dfs(int d)
 27 //{
 28 //    vis[d]=1;
 29 //    f[c][d]=1;
 30 //    node *p=e[d];
 31 //    while (p)
 32 //    {
 33 //        if (!vis[p->d])
 34 //            dfs(p->d);
 35 //        p=p->to;
 36 //    }
 37 //}
 38 
 39 //map<int,int> ma;
 40 
 41 int main()
 42 {
 43     node *p;
 44     int T,n,m,x,y,i,j;
 45     int head,tail,d;
 46     int num;
 47     bool v;
 48     scanf("%d",&T);
 49     while (T--)
 50     {
 51         scanf("%d%d",&n,&m);
 52         for (i=1;i<=n;i++)
 53             e[i]=0;
 54 //        ma.clear();
 55         num=0;
 56         while (m--)
 57         {
 58             scanf("%d%d",&x,&y);
 59 //            if (ma.find(x)!=ma.end())
 60 //                x=ma[x];
 61 //            else
 62 //                ma[x]=++num,x=num;
 63 //            if (ma.find(y)!=ma.end())
 64 //                y=ma[y];
 65 //            else
 66 //                ma[y]=++num,y=num;
 67 
 68 
 69             p=new node();
 70             p->d=y;
 71             p->to=e[x];
 72             e[x]=p;
 73         }
 74         for (c=1;c<=n;c++)
 75         {
 76 //            memset(vis,0,sizeof(vis));
 77 //            dfs(c);
 78 
 79             q[1]=c;
 80             vis[c]=1;
 81             head=0,tail=1;
 82             while (head<tail)
 83             {
 84                 head++;
 85                 d=q[head];
 86                 p=e[d];
 87                 while (p)
 88                 {
 89                     if (!vis[p->d])
 90                     {
 91                         vis[p->d]=1;
 92                         q[++tail]=p->d;
 93                         f[c][p->d]=1;
 94                     }
 95                     p=p->to;
 96                 }
 97             }
 98             for (j=1;j<=tail;j++)
 99                 vis[q[j]]=0;
100         }
101 
102         v=1;
103         for (i=1;i<=n;i++)
104             for (j=i+1;j<=n;j++)
105                 if (!f[i][j] && !f[j][i])
106                     v=0;
107         printf("%s
",v?"Yes":"No");
108     }
109     return 0;
110 }