885
poj 2942 Knights of the Round Table 點重聯通分量
書上把這放在邊聯通的第一道題，於是一開始就按邊寫了，一直寫不對，重新想了一遍，才發現是點聯通……
/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
#define pb push_back
using namespace std;
int n,m;
int Map[1005][1005];
vector<int> org[1005];
vector<int> belong[1005];
int vis[1005];
int dph[1005],low[1005];
int d;
int num=0;
bool ok[1005];
stack<int> S;
void dfs(int v,int f)
{
vis[v]=1;
dph[v]=low[v]=d++;
S.push(v);
for(int i=0; i<org[v].size(); i++)
{
int u=org[v][i];
if(u==f)continue;
if(vis[u]==1)low[v]=min(low[v],dph[u]);
else if(!vis[u])
{
dfs(u,v);
low[v]=min(low[v],low[u]);
if(low[u]>=dph[v])
{
num++;
belong[v].pb(num);
belong[u].pb(num);
while(S.top()!=u)// 注意邊界，如果吧push放在for循環裏就是!=v不用pop，否則就是!=u最後還要pop
{
belong[S.top()].pb(num);
S.pop();
}
S.pop();
}
}
}
vis[v]=2;
}
int Tarjan() //搜索重聯通分量
{
num=0;
while(!S.empty())S.pop();
for(int i=1; i<=n; i++)
{
d=0;
if(!vis[i])
dfs(i,-1);
}
}
int dye(int v,int c,int flag)//1,-1染色
{
vis[v]=c;
for(int i=0; i<org[v].size(); i++)
{
int &u=org[v][i];
if(ok[u])
{
if(vis[u]==0&&dye(u,-c,flag))return 1;
if(vis[u]==c)return 1;
}
}
return 0;
}
int use[1005];
int Count()
{
int ans=0;
memset(use,0,sizeof(use));
for(int k=1; k<=num; k++)
{
memset(ok,0,sizeof(ok));
memset(vis,0,sizeof(vis));
for(int i=1; i<=n; i++)
{
if(find(belong[i].begin(),belong[i].end(),k)!=belong[i].end())
ok[i]=1;
}
for(int i=1; i<=n; i++)
{
if(ok[i])
{
if(dye(i,1,k))
for(int j=1; j<=n; j++)
use[j]+=ok[j];
break;
}
}
}
for(int i=1; i<=n; i++)
if(!use[i])ans++;
return ans;
}
int main()
{
while(~scanf("%d%d",&n,&m)&&n+m)
{
int a,b;
int i,j;
memset(vis,0,sizeof(vis));
memset(Map,0,sizeof(Map));
for(i=1; i<=n; i++)
{
org[i].clear();
belong[i].clear();
Map[i][i]=1;
}
for(i=0; i<m; i++)
{
scanf("%d%d",&a,&b);
Map[a][b]=Map[b][a]=1;
}
for(i=1; i<=n; i++) //建立不憎恨的圖
{
for(j=i; j<=n; j++)
if(!Map[i][j])
{
org[i].pb(j);
org[j].pb(i);
}
}
Tarjan();
printf("%d\n",Count());
}
}
最後更新：2017-04-03 15:21:44