Problem Description

K國(guó)是一個(gè)熱衷三角形的國(guó)度,連人的交往也只喜歡三角原則.他們認(rèn)為三角關(guān)系:即AB相互認(rèn)識(shí),BC相互認(rèn)識(shí),CA
相互認(rèn)識(shí),是簡(jiǎn)潔高效的.為了鞏固三角關(guān)系,K國(guó)禁止四邊關(guān)系,五邊關(guān)系等等的存在.所謂N邊關(guān)系,是指N個(gè)人 A1A2
...An之間僅存在N對(duì)認(rèn)識(shí)關(guān)系:(A1A2)(A2A3)...(AnA1),而沒(méi)有其它認(rèn)識(shí)關(guān)系.比如四邊關(guān)系指ABCD四個(gè)人 AB,BC,C
D,DA相互認(rèn)識(shí),而AC,BD不認(rèn)識(shí).全民比賽時(shí),為了防止做弊，規(guī)定任意一對(duì)相互認(rèn)識(shí)的人不得在一隊(duì)，國(guó)王相知道，
最少可以分多少支隊(duì)。

Input

第一行兩個(gè)整數(shù)N，M。1<=N<=10000,1<=M<=1000000.表示有N個(gè)人，M對(duì)認(rèn)識(shí)關(guān)系. 接下來(lái)M行每行輸入一對(duì)朋
友

Output

輸出一個(gè)整數(shù)，最少可以分多少隊(duì)

Sample Input

4 5
1 2
1 4
2 4
2 3
3 4

Sample Output

3

思路：將 n 個(gè)人 m 個(gè)關(guān)系視為 n 個(gè)點(diǎn) m 條邊，從而構(gòu)成一個(gè)圖，根據(jù)關(guān)系的描述可知，構(gòu)成的圖是一個(gè)弦圖，而題目本質(zhì)上就是要求最小著色數(shù)，對(duì)于弦圖來(lái)說(shuō)，直接跑 MCS 后求取最大的 label[i]+1 即可

Source Program

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #include<bitset> #define PI acos(-1.0) #define INF 0x3f3f3f3f #define LL long long #define Pair pair<int,int> LL quickPow(LL a,LL b){ LL res=1; while(b){if(b&1)res*=a; a*=a; b>>=1;} return res; } LL quickModPow(LL a,LL b,LL mod){ LL res=1; a=a%mod; while(b){if(b&1)res=(a*res)%mod; a=(a*a)%mod; b>>=1;} return res; } LL getInv(LL a,LL mod){ return quickModPow(a,mod-2,mod); } const double EPS = 1E-10; const int MOD = 1E9+7; const int N = 1000000; const int dx[] = {-1,1,0,0,-1,-1,1,1}; const int dy[] = {0,0,-1,1,-1,1,-1,1}; using namespace std;struct Edge {int to,next;Edge() {}Edge(int to,int next):to(to),next(next) {} }; struct MCS{Edge edge[N<<1];int head[N],tot;int n,m;bool vis[N];int id[N];//編號(hào)int label[N];//與多少標(biāo)號(hào)點(diǎn)相鄰int order[N];//完美消除序列vector<int> V[N];void init(int n,int m) {this->n=n;this->m=m;for(int i=1; i<=n; i++)V[i].clear();memset(head,-1,sizeof(head));memset(order,0,sizeof(order));memset(label,0,sizeof(label));memset(vis,0,sizeof(vis));memset(id,0,sizeof(id));tot=0;}void addEdge(int x,int y) {edge[tot].to=y;edge[tot].next=head[x];head[x]=tot++;}void mcs() {for(int i=1; i<=n; i++)V[0].push_back(i);int maxx=0;int now=0;for(int i=1; i<=n; i++) { //從前往后bool flag=false;while(!flag) {for(int j=V[maxx].size()-1; j>=0; j--) { //從后往前if(vis[V[maxx][j]])V[maxx].pop_back();else {flag=true;now=V[maxx][j];break;}}if(!flag)maxx--;}vis[now]=true;//逆序存放order[n-i+1]=now;id[now]=n-i+1;for(int j=head[now]; j!=-1; j=edge[j].next) {int to=edge[j].to;if(!vis[to]) {label[to]++;V[label[to]].push_back(to);maxx=max(maxx,label[to]);}}}}int bucket[N];//桶int judge() { //判斷是否是弦圖memset(vis,0,sizeof(vis));memset(bucket,0,sizeof(bucket));for(int i=n; i>0; i--) {int cnt=0;int ret=1;for(int j=head[order[i]]; j!=-1; j=edge[j].next)if(id[edge[j].to]>i)vis[bucket[++cnt]=edge[j].to]=1;for(int j=head[bucket[1]]; j!=-1; j=edge[j].next) {int to=edge[j].to;if(to!=bucket[1]&&vis[to]) {if(vis[to]) {ret++;vis[to]++;}}}for(int j=1; j<=cnt; j++)vis[bucket[j]]=0;if(cnt&&ret!=cnt)return false;}return true;}int getMaximumClique() { //計(jì)算最大團(tuán)、最小著色int res=0;for(int i=1; i<=n; i++)res=max(res,label[i]+1);return res;}int getMaximumIndependentSet() { //計(jì)算最大獨(dú)立集、最小團(tuán)覆蓋memset(vis,0,sizeof(vis));int res=0;for(int i=1; i<=n; i++) {if(!vis[order[i]]) {res++;vis[order[i]]=true;for(int j=head[order[i]]; j!=-1; j=edge[j].next)vis[edge[j].to]=true;}}return res;} }mcs; int main() {int n,m;scanf("%d%d",&n,&m);mcs.init(n,m);for(int i=1; i<=m; i++) {int x,y;scanf("%d%d",&x,&y);mcs.addEdge(x,y);mcs.addEdge(y,x);}mcs.mcs();int res=mcs.getMaximumClique();//最大團(tuán)、最小著色printf("%d\n",res);return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的神奇的国度（HYSBZ-1006）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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