求助一道团队题目
  • 板块灌水区
  • 楼主shipeiqian
  • 当前回复8
  • 已保存回复8
  • 发布时间2022/7/18 21:07
  • 上次更新2023/10/27 19:39:03
查看原帖
求助一道团队题目
632063
shipeiqian楼主2022/7/18 21:07

rt,蒟蒻只得了60分,题目见下。

充满希望的连通块问题

题目描述

输入一个n个点m条边的图。然后输入两个整数x, y,判断结点x与结点y是否在同一个连通块中。

如果节点x与节点y在一个连通块中,输出该连通块内节点的数量,否则输出0。

输入格式

第一行输入两个整数 n,m(1n105,1m2105)n, m(1\leq n \leq 10^5, 1 \leq m \leq 2 * 10^5)

接下来m行,每行输入两个整数 u,v(1u,vn)u, v ( 1\leq u , v \leq n) 表示点u与v之间有一条无向边。

最后一行输入两个整数x,y(1x,yn)x, y (1\leq x,y\leq n)

输出格式

输出一个整数。如果节点x与节点y在一个连通块中,输出该连通块内节点的数量,否则输出0。

样例 #1

样例输入 #1

5 3
1 2
1 3
4 5
2 3

样例输出 #1

3

样例 #2

样例输入 #2

5 3
1 2 
1 3
4 5
2 4

样例输出 #2

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

2022/7/18 21:07
加载中...