1008. Airline Routes (35)
Given a map of airline routes, you are supposed to check if a round trip can be planned between any pair of cities.
Input Specification:
Each input file contains one test case. For each case, the first line gives two positive integers N (2<= N <= 104) and M (<=6N), which are the total number of cities (hence the cities are numbered from 1 to N) and the number of airline routes, respectively. Then M lines follow, each gives the information of a route in the format of the source city index first, and then the destination city index, separated by a space. It is guaranteed that the source is never the same as the destination.
After the map information, another positive integer K is given, which is the number of queries. Then K lines of queries follow, each contains a pair of distinct cities' indices.
Output Specification:
For each query, output in a line "Yes" if a round trip is possible, or "No" if not.
Sample Input:
12 19
3 4
1 3
12 11
5 9
6 2
3 2
10 7
9 1
7 12
2 4
9 5
2 6
12 4
11 10
4 8
8 12
11 8
12 7
1 5
20
11 4
12 7
3 6
2 3
5 3
3 9
4 3
8 3
8 10
10 11
7 8
7 1
9 5
1 9
2 6
3 1
3 12
7 3
6 9
6 8
Sample Output:
Yes
Yes
No
No
No
No
No
No
Yes
Yes
Yes
No
Yes
Yes
Yes
No
No
No
No
No
题目链接：PAT (Top Level) Practise 1008
给m组单向边和k个询问，每次询问两个点是否互相可达……学完Tarjan就来想做这个以前一直不会的模版题了，用sc表示当前检测到的连通分量个数，belong[]数组表示当前点属于第几个连通分量，至于如何Tarjan，画个图比较好理解，DFS这种东西真是只可意会不可言传
代码：
#include <stdio.h>
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
typedef pair<int,int> pii;
typedef long long LL;
const double PI=acos(-1.0);
const int N=1e4+7;
const int M=6e4+7;
struct edge
{
int to;
int pre;
};
edge E[M];
int head[N],tot;
int ins[N],low[N],dfn[N],st[N],top,belong[N];
int ts,sc; inline void add(int s,int t)
{
E[tot].to=t;
E[tot].pre=head[s];
head[s]=tot++;
}
void init()
{
CLR(head,-1);
tot=0;
CLR(ins,0);
CLR(low,0);
CLR(dfn,0);
ts=0;
top=0;
sc=0;
CLR(belong,-1);
}
void tar(int u)
{
dfn[u]=low[u]=++ts;
st[top++]=u;
ins[u]=1;
int v;
for (int i=head[u]; ~i; i=E[i].pre)
{
v=E[i].to;
if(!dfn[v])
{
tar(v);
low[u]=min<int>(low[u],low[v]);
}
else if(ins[v])
low[u]=min<int>(low[u],dfn[v]);
}
if(dfn[u]==low[u])
{
++sc;
do
{
v=st[--top];
ins[v]=0;
belong[v]=sc;
}while (u!=v);
}
}
int main(void)
{
int n,m,a,b,i,k;
while (~scanf("%d%d",&n,&m)&&(n||m))
{
init();
for (i=0; i<m; ++i)
{
scanf("%d%d",&a,&b);
add(a,b);
}
for (i=1; i<=n; ++i)
if(!dfn[i])
tar(i);
scanf("%d",&k);
for (i=0; i<k; ++i)
{
scanf("%d%d",&a,&b);
puts(belong[a]==belong[b]?"Yes":"No");
}
}
return 0;
}