rt,蒟蒻只得了60分,题目见下。
输入一个n个点m条边的图。然后输入两个整数x, y,判断结点x与结点y是否在同一个连通块中。
如果节点x与节点y在一个连通块中,输出该连通块内节点的数量,否则输出0。
第一行输入两个整数 n,m(1≤n≤105,1≤m≤2∗105)。
接下来m行,每行输入两个整数 u,v(1≤u,v≤n) 表示点u与v之间有一条无向边。
最后一行输入两个整数x,y(1≤x,y≤n)。
输出一个整数。如果节点x与节点y在一个连通块中,输出该连通块内节点的数量,否则输出0。
5 3
1 2
1 3
4 5
2 3
3
5 3
1 2
1 3
4 5
2 4
0
这是蒟蒻的代码:
#include <iostream>
#include <vector>
using namespace std;
int y,x,ans=0;
vector<int> e[200005];
bool visited[200005];
bool found=false;
void dfs(int x) {
visited[x]=true;
if (x==y) {
ans++;
found=true;
}
for(int i=0;i<e[x].size();i++){
int nxt=e[x][i];
if(!visited[nxt])dfs(nxt);
}
return ;
}
int main(){
int n,m;
cin >>n >>m;
for(int i=1;i<=m;i++){
int u,v;
cin >>u >>v;
e[u].push_back(v);
e[v].push_back(u);
}
cin >>x >>y;
dfs(x);
if(found)cout <<ans;
else cout <<0;
return 0;
}
dalao帮帮忙Orz