Portal:http://codeforces.com/problemset/problem/506/B
http://codeforces.com/problemset/problem/505/D
好题
给n个城市，m条有向边，求出最少的有向边使得其构成的图与原图等势
对于每个连通分量：
如果无环，那么只需要需要n-1条边完成联通
如果有环，则只需要n条边完成联通
所以这题只要判下连通分量，再看有几个连通分量有环即可
解法一：无向图遍历求强连通分量再把强连通分量所代表的联通分量dfs判环，如下
| Memory: 10440 KB | Time: 498 MS |
#include<iostream>
#include<algorithm>
#include<set>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<vector>
using namespace std;
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define FORD(i,j,k) for(int i=j;i>=k;i--)
#define LL long long
#define SZ(x) int(x.size())
#define maxn 100010
int n,m,x,y;
bool circle=true;
int vis[maxn],vis2[maxn];
vector<int> neg[maxn],adj[maxn];
vector<int> dot;
void ndfs(int start)
{
dot.push_back(start);
vis[start]=;
FOR(i,,SZ(neg[start])-)
{
if(!vis[neg[start][i]]) ndfs(neg[start][i]); }
return;
}
void adfs(int start)
{
vis2[start]=;
FOR(i,,SZ(adj[start])-)
{
if(!vis2[adj[start][i]]) adfs(adj[start][i]);
else if(vis2[adj[start][i]]==)circle=false;
}
vis2[start]=;
return;
}
int main()
{
cin>>n>>m;
FOR(i,,m)
{
cin>>x>>y;
neg[x].push_back(y);
neg[y].push_back(x);
adj[x].push_back(y);
}
int ans=n;
FOR(i,,n)
{
circle=;
if(!vis[i])
{
dot.clear();
ndfs(i);
FOR(i,,SZ(dot)-)
if (!vis2[dot[i]]) adfs(dot[i]);
ans-=circle;
}
}
cout<<ans<<endl;
return ;
}
我在想函数名字到底取afs好还是adfs好
解法二：在无向图中维护并查集求强连通分量再把强连通分量所代表的联通分量用拓扑排序判环，如下
| Memory: 7820 KB | Time: 514 MS |
#include<iostream>
#include<algorithm>
#include<set>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<vector>
using namespace std;
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define FORD(i,j,k) for(int i=j;i>=k;i--)
#define LL long long
#define SZ(x) int(x.size())
#define maxn 100010
vector<int> G[maxn];
int n,m,x,y,T;
int father[maxn],val[maxn],circle[maxn],vis[maxn],clock[maxn];
int setfind(int x)
{
int fa=father[x];
if(fa==x) return x;
else return father[x]=setfind(fa);
}
void setunion(int x,int y)
{
int X=setfind(x);
int Y=setfind(y);
if(X==Y) return;
if(val[X]>val[Y]) father[Y]=X;
else father[X]=Y;
if(val[X]==val[Y]) val[X]++;
return;
}
void dfs(int start)
{
vis[start]=;
FOR(i,,SZ(G[start])-)
if(!vis[G[start][i]]) dfs(G[start][i]);
clock[start]=++T;
return;
}
int main()
{
cin>>n>>m;
FOR(i,,n)
{father[i]=i;val[i]=;}
FOR(i,,m)
{
cin>>x>>y;
G[x].push_back(y);
setunion(x,y);
}
FOR(i,,n)
if(!vis[i]) dfs(i);
FOR(i,,n)
FOR(j,,SZ(G[i])-)
if(clock[i]<clock[G[i][j]]) circle[setfind(i)]=;
int ans=n;
FOR(i,,n)
if(i==setfind(i))if(!circle[setfind(i)]) ans--;
cout<<ans<<endl;
return ;
}
Mr. Kitayuta's Black Technology
其实求连通分量还可以用染色
判有向环可以用并查集乱搞
反正就是怎么搞都能过