解题报告
题目
：http://poj.org/problem?id=1236
题目大意
：给定一个有向图，求下面两个量：
1
：最少从几个点出发能遍历全图。
2
：最少加几条边能使原图强联通。
算法
：tarjan求强联通分量
思路
：“最少从几个点出发能遍历全图”的点数是将原图缩点后入度为零的点的个数。
“最少加几条边能使原图强联通”的边数是将原图缩点后出度为零的点和入读为零的点中的最大值。
注
：当只有一个缩点时，边数为0.
提交情况
：wrong answer
2次
（边数求成了出度为零的点的个数。。）
1次
//poj2553也是类似题
AC
code：
#include <stdio.h>
#include <string.h>
#define MAXN 2000
#define MAXM (MAXN * MAXN)
struct NODE{
int to, next;
};
NODE edges[MAXM];
inthead[MAXN], ad;
intdfn[MAXN], low[MAXN], vis[MAXN], strack[MAXN],
belong[MAXN], in[MAXN], out_degree[MAXN],
in_degree[MAXN];
int times, tarjan_total, top;
void dfs(int
u){
int p;
low[u] = dfn[u] = times ++;
strack[++top] = u;
vis[u] = 1;
in[u] = 1;
for(p = head[u];
edges[p].next){
if(!vis[edges[p].to]){
dfs(edges[p].to);
if(low[u] >
low[edges[p].to])
low[u] = low[edges[p].to];
}
else
if(in[edges[p].to]
&& low[u] >
low[edges[p].to]) low[u] = low[edges[p].to];
}
if(dfn[u] == low[u]){
tarjan_total ++;
belong[u] = tarjan_total;
in[u] = 0;
while((p = strack[top--]) !=
u){
low[p] = low[u];
belong[p] = tarjan_total;
in[p] = 0;
}
}
}
void tarjan(int
n){
int i;
times = 0;
tarjan_total = 0;
top = -1;
memset(vis, 0 ,sizeof(vis));
memset(in, 0, sizeof(in));
for(i = 1; i <= n; i
++)
if(!vis[i]) dfs(i);
}
void Getans(int
n){
int i, j;
memset(in_degree, 0, sizeof(in_degree));
memset(out_degree, 0, sizeof(out_degree));
for(i = 1; i <= n; i
++)
for(j = head[i]; ~j; j =
edges[j].next){
if(belong[i] !=
belong[edges[j].to]){
out_degree[belong[i]] ++;
in_degree[belong[edges[j].to]] ++;
}
}
int ans1 = 0, ans2 = 0;
for(i = 1; i <=
tarjan_total; i ++){
if(in_degree[i] == 0) ans1
++;
if(out_degree[i] == 0) ans2
++;
}
if(tarjan_total == 1) ans2 =
0;
else ans2 = ans1 >
ans2 ? ans1 : ans2;
printf("%d\n%d\n", ans1,
ans2);
}
int main(){
int n, t, i;
while(~scanf("%d", &n)){
ad = 0;
memset(head, -1, sizeof(head));
for(i = 1; i <= n; i
++)
while(~scanf("%d", &t), t){
edges[ad].to = t; edges[ad].next = head[i]; head[i] = ad
++;
}
tarjan(n);
Getans(n);
}
return 0;
}