救命,我被图淹没了

救命!!
帮我看看有没有什么错误!!
帮我看看批注的地方补什么代码!!

时间: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;
}
11 个赞

image
你这代码本来就是CE的啊

10 个赞

你是真的

6

11 个赞

hhhhhh

9 个赞

判断邻接表里有没有就行了,还有第三个写错了

9 个赞

666

8 个赞

认真的吗?
发伪代码(震惊) :open_mouth:

8 个赞

那个,没人解决的话我可以试试
Code:

#include<bits/stdc++.h>
using namespace std;
int n,m,ans[1000020];
vector<int> a[1000015];
int main(){
	ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
	cin>>n>>m;
	int u,v;
	for(int i=1;i<=m;i++){
		cin>>u>>v;
		if(u==v) continue;
		a[u].push_back(v);
		a[v].push_back(u);
	}
	for(int i=1;i<=n;i++){
		ans[a[i].size()]++;
	}
	if(ans[2]==n){
		cout<<"Ring";
	}
	else if(ans[n-1]==1&&ans[1]==n-1){
		cout<<"Flower";
	}
	else if(ans[2]==n-2&&ans[1]==2){
		cout<<"Chain";
	}
	else{
		cout<<"Neither";
	}
}

敲了两年半

4 个赞

求解决方案

1 个赞