第一问是求最小基点，采用两点DFS的kosaraju算法，对每个点进行DFS，标记visited为true，然后对反图再进行DFS，能遍历到的点属于一个强连通分量。 （强连通分量上的边，求反之后，是仍然可以遍历到的，反图其实是过滤了非强连通的边）
然后把强连通分量收缩成一个点，构造新图。新图中，入度为0的点的个数就是最小基点。
第二问，若一个顶点入度为0或者出度为0的时候，该图一定不是强连通的。为了使添加的边最少，则应该把入度为0顶点和出度为0的顶点每个顶点添加1条边，使图中不存在入度为0顶点和出度为0的顶点。新图中，入度为0的点的个数为s1，出度为0的点的个数s2，求max(s1,s2)。
/**//*
ID: lorelei3
TASK: schlnet
LANG: C++
*/
#include <fstream>
#include <memory.h>
using namespace std;
const int MAXN = 105;
ifstream fin("schlnet.in");
ofstream fout("schlnet.out");
int adj[MAXN][MAXN], fadj[MAXN][MAXN], dist[MAXN][MAXN];
int belong[MAXN], ind[MAXN], outd[MAXN];
bool visited[MAXN];
int M,id,od;
void dfs(int k)
{
visited[k]=true;
for(int i=1; i<=adj[k][0]; ++i){
int j=adj[k][i];
if(!visited[j])
dfs(j);
}
}
void fdfs(int k){
belong[k]=M;
for(int i=1; i<=fadj[k][0]; ++i){
int j=fadj[k][i];
if(visited[j]&&!belong[j])
fdfs(j);
}
}
int n;
void solve(){
int i,j,k;
//kosaraju
for(i=1; i<=n; ++i){
if(!belong[i]){
dfs(i);
M++;
fdfs(i);
memset(visited, false, sizeof(visited));
}
}
for(i=1; i<=n; ++i)
for(k=1; k<=adj[i][0]; ++k){
int j=adj[i][k];
dist[belong[i]][belong[j]]=true;
}
for(i=1; i<=M; ++i)
for(j=1; j<=M; ++j)
if(i!=j&&dist[i][j]){
outd[i]++;
ind[j]++;
}
for(i=1; i<=M; ++i){
if(ind[i]==0)
id++;
if(outd[i]==0)
od++;
}
}
void input(){
fin>>n;
for(int i=1; i<=n; ++i){
int a;
fin>>a;
while(a!=0){
adj[i][++adj[i][0]]=a;
fadj[a][++fadj[a][0]]=i;
fin>>a;
}
}
}
void output(){
if(M==1)
fout<<1<<endl<<0<<endl;
else{
fout<<id<<endl;
fout<<(id>od?id:od)<<endl;
}
}
int main(){
input();
solve();
output();
return 0;
}
posted on 2011-02-11 19:40
小阮 阅读(333)
评论(0) 编辑 收藏 引用 所属分类:
USACO