題目描述?

“サーヴァント、キャスター、Medea。”--紫魔法師

?

給出一棵仙人掌(每條邊最多被包含于一個(gè)環(huán)，無(wú)自環(huán)，無(wú)重邊，保證連通)，要求用最少的顏色對(duì)其頂點(diǎn)染色，滿足每條邊兩個(gè)端點(diǎn)的顏色不同，輸出最小顏色數(shù)即可

輸入描述:

第一行包括兩個(gè)整數(shù)n,m，表示頂點(diǎn)數(shù)和邊數(shù) n <= 100000, m <= 200000 接下來(lái)m行每行兩個(gè)整數(shù)u,v，表示u,v之間有一條無(wú)向邊，保證數(shù)據(jù)合法

輸出描述:

一行一個(gè)整數(shù)表示最小顏色數(shù)

示例1

輸入

復(fù)制

3 4 1 2 2 3 3 4 1 4

輸出

復(fù)制

2

這個(gè)題目數(shù)據(jù)很水，我看著有些人的代碼是生成隨機(jī)數(shù)的代碼，也過(guò)了。。。。

不過(guò)還是按照題目的要求來(lái)吧！畢竟那東西不是自己的真實(shí)水平。。。當(dāng)然我也很菜。。

閑話少說(shuō)上代碼：

#include <bits/stdc++.h>
using namespace std;
vector<int>mp[100005];///數(shù)據(jù)太大用的vector，不是很熟。。。
int n,m;
bool vis[100005];///標(biāo)記點(diǎn)有沒(méi)有訪問(wèn)過(guò)
bool col[100005];///顏色
int f = 0;///看看是不是存在奇數(shù)的環(huán)。
void dfs(int v0)
{
? ? for(int i=0; i<mp[v0].size(); i++)
? ? {
? ? ? ? int v = mp[v0][i];
? ? ? ? if(vis[v]==false)
? ? ? ? {
? ? ? ? ? ? vis[v] = true;
? ? ? ? ? ? col[v] = !col[v0];///標(biāo)記成不同的顏色。。
? ? ? ? ? ? dfs(v);///繼續(xù)找。
? ? ? ? }
? ? ? ? else
? ? ? ? {
? ? ? ? ? ? if(col[v]==col[v0])///如果相鄰的點(diǎn)是相同的顏色，就存在奇數(shù)環(huán)（就是一個(gè)環(huán)中有奇數(shù)個(gè)點(diǎn)）。
? ? ? ? ? ? {
? ? ? ? ? ? ? ? f = 1;
? ? ? ? ? ? ? ? return;
? ? ? ? ? ? }
? ? ? ? }
? ? }
}
int main()
{
? ? int u,v;
? ? scanf("%d%d",&n,&m);
? ? for(int i=0; i<m; i++)
? ? {
? ? ? ? scanf("%d%d",&u,&v);
? ? ? ? mp[u].push_back(v);
? ? ? ? mp[v].push_back(u);
? ? }
? ? if(n<2)
? ? ? ? printf("1\n");///一個(gè)點(diǎn)就一種顏色。
? ? else
? ? {
? ? ? ? col[1]=true;
? ? ? ? dfs(1);
? ? ? ? if(f)///cun zai ji huan
? ? ? ? ? ? printf("3\n");///按照題目中的要求來(lái)的話，最多圖3種顏色。（具體不再證明）
? ? ? ? else printf("2\n");
? ? }
? ? return 0;
}
?

?

總結(jié)

以上是生活随笔為你收集整理的牛客网+紫魔法师+染色问题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。