![](https://csdnimg.cn/release/download_crawler_static/4780367/bg5.jpg)
ACM
ACM
ACM
ACM 算法资料集锦 2009
2009
2009
2009 年 12
12
12
12 月 10
10
10
10 日星期四
5
for(i=1;i<=n;i++){
int p=findp(set,i);
if(sc[p].p==0) {sc[p].p=pi; ptosc[pi++]=p;}
sc[p].n++;
}
int n2=pi-1,od[M];
memset(od,0,sizeof(od));
for(i=1;i<=n;i++){
for(j=0;j<g[i].size();j++){
u=findp(set,i); v=findp(set,g[i][j]);
if(sc[u].p!=sc[v].p) od[sc[u].p]++;
}
}
int sum=0,s1=0;
for(i=1;i<=n2;i++) if(od[i]==0) {s1++; sum+=sc[ptosc[i]].n;}
if(s1!=1) sum=0;
cout << sum << endl;
}
最大匹配
#include <iostream>
#include <string>
#include <math.h>
using namespace std;
#define M 1001
int n,m,match[M],ans[M];
bool visit[M],g[M][M];
// O(n^3)
bool dfs(int k,bool map[M][M]){
int t;
for(int i = 1; i <= m; i++){
if(map[k][i] && !visit[i]){
visit[i] = true;
t = match[i];
match[i] = k;
if(t == 0
||
dfs(t,map))
return true;
match[i] = t;
}
}
return false;
}
int main(){
int i,sum=0,t,j,u,v;
cin >> t;
while(t--){
sum=0;
memset(match,0,sizeof(match));
memset(g,0,sizeof(g));
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++){
scanf("%d%d",&u,&v);
g[u][v]=true;
}
m=n;
for(i=1;i<=n; i++){
memset(visit,0,sizeof(visit));
if(dfs(i,g)) sum++;
}
cout << n-sum << endl;
}
return 0;
}
还有两个最大匹配模板
#include <iostream>
#include <string>
#include <math.h>
#include <vector>
using namespace std;
#define M 3001
bool g[M][M];
int mk[M] ,cx[M],pred[M],open[M],cy[M],nx,ny;
// 边少适用 O(n^3)
int MaxMatchBFS()
{
int i , u , v , t , d , e , cur , tail , res(0) ;
memset(mk , 0xff , sizeof(mk)) ;
memset(cx , 0xff , sizeof(cx)) ;
memset(cy , 0xff , sizeof(cy)) ;
for (i = 0 ; i < nx ; i++){
pred[i] = -1 ;
for (open[cur = tail = 0] = i ; cur <= tail && cx[i] == -1 ;
cur++){
for (u = open[cur] , v = 0 ; v < ny && cx[i] == -1 ; v ++) if
(g[u][v] && mk[v] != i)
{
mk[v] = i ; open[++tail] = cy[v] ; if (open[tail] >= 0)
{ pred[open[tail]] = u ; continue ; }
for (d = u , e = v ; d != -1 ; t = cx[d] , cx[d] = e , cy[e] =
d , e = t , d = pred[d]) ;
}
}
if (cx[i] != -1) res++ ;