救命!!
帮我看看有没有什么错误!!
帮我看看批注的地方补什么代码!!
时间:1s 空间:128M
题目描述:
在知道了图是什么样子之后,我们还需要知道图有哪些类型。
比赛中常常出现的图的类型有:
- 菊花图(即所有点都只和同一个点相连);
- 链图(即所有点形成了一条链);
- 简单环(即所有点连成了一个环)。
给出一张无向连通图,没有重边和自环,判断这张图是否是一个链图、简单环或者是菊花图,或者什么都不是。
输入格式:
第一行包含两个正整数 N 和 M,表示有 N 个点,M 条边。
接下来 M 行每行包含两个用空格隔开的正整数 u,v,表示一条从 u 到 v 的无向路径。
输出格式:
如果是菊花图,则输出 Flower;如果是链,则输出 Chain;如果是简单环,则输出 Ring;否则输出Neither。
样例输入:
4 3 1 2 3 4 2 3
样例输出:
Chain
约定:
4≤N,M≤106
伪代码如下:
#include<bits/stdc++.h>
using namespace std;
int n,m,x,y;
vector<int> a[1000005];
bool is_flower(int x,int y){
for(int i=0;i<m;i++){
if(/*根节点和当前点相连*/) is_flower(x,y+1);
else return false;
}
return true;
}
bool is_chain(int x,int y){
for(int i=0;i<m;i++){
if(/*当前点和上一点相连*/) is_chain(x+1,y+1);
else return false;
}
return true;
}
bool is_ring(int x,int y){
for(int i=0;i<m;i++){
if(/*当前点和上一点相连*/) is_chain(x+1,y+1);
else return false;
}
if(/*最后一点和第一点相连*/){
return true;
}else{
return false;
}
}
int main(){
cin>>n>>m;
while(m--){
scanf("%d%d",&x,&y);
a[x].push_back(y);
a[y].push_back(x);
}
if(is_flower(-1,0)==true) cout<<"Flower";
if(is_chain(-1,0)==true) cout<<"Chain";
if(is_ring(-1,0)==true) cout<<"Ring"
if(is_flower(-1,0) and is_chain(-1,0) and is_ring(-1,0)){
cout<<"Neither";
}
return 0;
}