比较综合的一道题目...题意是在一个有向图中给出点的数目和一些点对的可达条件,求最少可以使用多少条边来满足这些条件
比如题目给出一个条件1 2,即1可达2,那么可以用一条边1->2来满足,或者用1->3,3->2两条边来满足但是这样可以新多出两个可达点对即 1 3,3 2
思路:首先如果一个包含n个点无环的连通图,那么至少得需要n-1条边来构造.如果一个包含n个点有环的连通图,那么我们可以用n条边来构造一个首尾相连
的环图,这样所有点之间都可达.至此对于一个包含n个点的连通图而言,所需最少边数不是n-1就是n,取决于该图是否有环
如果给出的不只是一个连通图呢？好,我们可以根据公式k=n-x+y来确定所需的最少边数,其中k是最少需要的边数,x是连通图的数量,y是环的数量
对于一个连通图我们只需要确定是否有环,而不用确定有多少个环,那么y<=x.
至此思路已经明确:1.将所有点划分至各个连通图当中(求连通数) 2.对各个连通分量进行判断是否有环(求环数)
对于1我们可以用dfs来遍历无向图来划分点.
对于2我们得出划分后,对各个连通图进行拓扑排序,可以判断是否有环.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int indegree[100100];
int outdegree[100100];
int use[100100];
int use2[100100];
vector<int> graph[100100];
vector<int> graph2[100100];
vector<int> G[100100];
int num=0;
queue<int> q;
void dfs(int v)
{
for(int i=0;i<graph2[v].size();i++)
{
if(use[graph2[v].at(i)]==0)
{
use[graph2[v].at(i)]=1;
G[num].push_back(graph2[v].at(i));
dfs(graph2[v].at(i));
}
}
}
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int u,v;
cin>>u>>v;
graph[u].push_back(v);
graph2[u].push_back(v);
graph2[v].push_back(u);
indegree[v]++;
outdegree[u]++;
}
for(int i=1;i<=n;i++)
{
if(!use[i])
{
num++;
use[i]=1;
G[num].push_back(i);
dfs(i);
}
}
int res2=0;
for(int i=1;i<=num;i++)
{
queue<int> q;
for(int j=0;j<G[i].size();j++)
{
if(indegree[G[i].at(j)]==0)
{
q.push(G[i].at(j));
}
}
while(!q.empty())
{
int k=q.front();
q.pop();
use2[k]=1;
for(int j=0;j<graph[k].size();j++)
{
indegree[graph[k].at(j)]--;
outdegree[k]--;
if(indegree[graph[k].at(j)]==0&&!use2[graph[k].at(j)])
{
q.push(graph[k].at(j));
}
}
}
for(int j=0;j<G[i].size();j++)
{
if(use2[G[i].at(j)]==0)
{
res2++;
break;
}
}
}
cout<<n-num+res2<<endl;
return 0;
}
原文：http://www.cnblogs.com/wzsblogs/p/4290033.html