WA90求助

常规
1 
给你t张有向图，请你判断每张图是否是一颗树.

输入格式
第一行包含一个正整数t(1≤t≤2000),表示测试数据组数
对于每个测试数据，第一行包含两个整数n和m(2≤n≤200000;1≤m≤200000,表示图的点数和边数.
接下来m行每行包含两个整数u和v(1≤u,v≤n,u≠v),代表一条u指向v的边.
数据保证没有重边和自环.
对于所有测试数据，数据总量不超过2∗105.

输出格式
对于每个测试数据，输出"Case k is a tree."如果第k个测试数据是一棵树，否则输出"Case k is not a tree."

样例#1
样例输入#1
3
6 5
5 6
4 2
4 1
5 3
4 5
9 8
8 1
7 3
6 2
8 9
7 5
7 4
7 8
7 6
6 6
2 6
5 6
5 3
4 2
4 5
4 1
样例输出#1
Case 1 is a tree.
Case 2 is a tree.
Case 3 is not a tree.

我的思路是，每次输入u、v的时候把f[v]++，也就是统计每个人父节点的个数（毕竟他是张有向图），然后先判断n是否等于m+1，如果不等于那直接输出Case k is not a tree.等于则继续判断。然后遍历f数组如果f[i]>1，也就是有多个父亲，则输出Case k is not a tree.如果每个点都只有一个父亲（除第一个节点），则输出Case k is a tree.

2 个赞
3

这里或许有你想要的

1 个赞
4

那个九十分的更好

1 个赞
5

还有你的代码呢

1 个赞
6 
#include<bits/stdc++.h>
using namespace std;
int t,n,m;
bool flag;
int f[200005];
int main(){
	cin>>t;
	for(int k=1;k<=t;k++){
		flag=0;
		cin>>n>>m;
		memset(f,0,sizeof(f));
		for(int i=1;i<=m;i++){
			int u,v;
			cin>>u>>v;
			f[v]++;
		}
		if(n!=(m+1)){
			cout<<"Case "<<k<<" is not a tree.\n";
			continue;
		}
		for(int i=1;i<=n;i++){
			if(f[i]>1){
				cout<<"Case "<<k<<" is not a tree.\n";
				flag=1;
				break;
			}
		}
		if(!flag) cout<<"Case "<<k<<" is a tree.\n";
	}
	return 0;
}
1 个赞
7

image

1 个赞
8

那你不就相当于把u当成空气吗

1 个赞
9

1 个赞
10

他可不保证一定连通啊

1 个赞
11

我判断了n是否等于m+1（大雾

1 个赞
12

你要先看 m 是否等于 n-1
然后再看是否联通

1 个赞
13

那也不行

1 个赞
14

o知道了

1 个赞
15

所以解决方案给谁

1 个赞
16

我我我

1 个赞
17

呃呃

1 个赞
18

@栗子酱 此帖结

1 个赞