![](https://csdnimg.cn/release/download_crawler_static/12732125/bg14.jpg)
top2 = 0;
/*Main*/
nPart = 0;
}
//FUNCTION:
//Number of SCC
void QueryNp()
{
printf("%d\n", nPart);
}
//Rebuild the Graph with SCC
bool ava[V][V];
void Rebuild(int Nv)
{
memset(ava, 0, sizeof(ava));
for (node *tp = pool; tp != pp; tp ++)
ava[belong[tp->u]][belong[tp->v]] = true;
for (int i = 1; i <= Nv; i ++) ava[i][i] = true;
}
void Floyd()
{
for (int k = 1; k <= nPart; k ++)
for (int i = 1; i <= nPart; i ++)
if (ava[i][k])
for (int j = 1; j <= nPart; j ++)
if (ava[k][j]) ava[i][j] = true;
}
int main()
{
while (scanf("%d%d", &v, &e) == 2 )
{
init(v);
while (e --)
{
int a, b;
scanf("%d%d", &a, &b);
adj[a] = Add_Edge(a, b, adj[a]);
}
for (int i = 1; i <= v; i ++)
if (low[i] == MAX) DFS(i);
Rebuild(v);
Floyd();
int Q;
scanf("%d", &Q); ////询问次数
while (Q --)
{
int a, b;
scanf("%d%d", &a, &b); ////询问哪两个点是否可连通
if (ava[belong[a]][belong[b]]) printf("Yes\n");
else printf("No\n");
}
}
return 0;
}
/*==================================================*\
| 无向图连通分支(dfs/bfs 邻接阵)
| DFS / BFS / 并查集
\*==================================================*/
/*==================================================*\
| 有向图强连通分支(dfs/bfs 邻接阵)O(n^2)
\*==================================================*/
//返回分支数,id 返回 1..分支数的值
//传入图的大小 n 和邻接阵 mat,不相邻点边权 0
#define MAXN 100
void search(int n,int mat[][MAXN],int* dfn,int* low,int
now,int& cnt,int& tag,int* id,int* st,int& sp){
int i,j;
dfn[st[sp++]=now]=low[now]=++cnt;
for (i=0;i<n;i++)
if (mat[now][i]){
if (!dfn[i]){
search(n,mat,dfn,low,i,cnt,tag,id,st,sp);
if (low[i]<low[now])
low[now]=low[i];
}
else if (dfn[i]<dfn[now]){
for (j=0;j<sp&&st[j]!=i;j++);
if (j<cnt&&dfn[i]<low[now])
low[now]=dfn[i];
}
}
if (low[now]==dfn[now])
for (tag++;st[sp]!=now;id[st[--sp]]=tag);
}
int find_components(int n,int mat[][MAXN],int* id){
int ret=0,i,cnt,sp,st[MAXN],dfn[MAXN],low[MAXN];
for (i=0;i<n;dfn[i++]=0);
for (sp=cnt=i=0;i<n;i++)
if (!dfn[i])
search(n,mat,dfn,low,i,cnt,ret,id,st,sp);
return ret;
}
//有向图强连通分支,bfs 邻接阵形式,O(n^2)
//返回分支数,id 返回 1..分支数的值
//传入图的大小 n 和邻接阵 mat,不相邻点边权 0
#define MAXN 100
int find_components(int n,int mat[][MAXN],int* id){
int ret=0,a[MAXN],b[MAXN],c[MAXN],d[MAXN],i,j,k,t;
for (k=0;k<n;id[k++]=0);
for (k=0;k<n;k++)
if (!id[k]){
for (i=0;i<n;i++)
a[i]=b[i]=c[i]=d[i]=0;
a[k]=b[k]=1;
for (t=1;t;)
for (t=i=0;i<n;i++){
if (a[i]&&!c[i])
for (c[i]=t=1,j=0;j<n;j++)
if (mat[i][j]&&!a[j])
a[j]=1;
if (b[i]&&!d[i])
for (d[i]=t=1,j=0;j<n;j++)
if (mat[j][i]&&!b[j])
b[j]=1;
}
for (ret++,i=0;i<n;i++)
if (a[i]&b[i])
id[i]=ret;
}
return ret;
}
/*==================================================*\
| 有向图最小点基(邻接阵)O(n^2)
| 点基 B 满足:对于任意一个顶点 Vj,一定存在 B 中的一个 Vi,使得 Vi
是 Vj 的前代。
|返回点基大小和点基
|传入图的大小 n 和邻接阵 mat,不相邻点边权 0
|需要调用强连通分支
\*==================================================*/
#define MAXN 100
int base_vertex(int n,int mat[][MAXN],int* sets){
int ret=0,id[MAXN],v[MAXN],i,j;
j=find_components(n,mat,id);
for (i=0;i<j;v[i++]=1);
for (i=0;i<n;i++)
for (j=0;j<n;j++)
if (id[i]!=id[j]&&mat[i][j])
v[id[j]-1]=0;
for (i=0;i<n;i++)
if (v[id[i]-1])
v[id[sets[ret++]=i]-1]=0;
return ret;
}