Home > OI > poj 1144

poj 1144


这题是求割点,参考《图论的算法与程序设计》中的算法即可

提供两个数据

1.in
21
17 4 18
1 11
7 5
13 1
3 1
14 5
15 20
9 12
6 8
16 14
18 8
8 4
20 18 10
2 3
12 5
5 9 20
19 20 9 11 2
11 3
4 15
10 3
21 3
0

1.out
6

2.in
63
30 11 33 52 9 25 47 28 59 29 32 18 7 35
51 15
19 47 25
32 27
9 46
7 59
13 53
35 17
6 2
63 21 35
52 40
4 58
27 61
43 54
49 16
11 44
25 57
60 54
21 35
23 41 50 11 2 25 3
59 1
33 41 15
53 57
22 62
57 19
34 7
44 46 39 57
48 29 3
47 48
18 29 25
10 38
62 25
56 23 8 62 46 30 6 44 43 60 29 45 26
3 6
40 12 31
38 45 22
8 11 43 13 49 18
14 49
55 10
5 49
28 3 14 61 20 24
54 35
29 5
46 31
45 44
17 54 19
39 61 58 2 26
61 37
1 52 58
12 62 31 56 43 28 61
36 12
58 44
26 29
31 3
50 52 6 28
16 10 51 25
20 54 47 13 29 4 6 44 52 32 53 39 57 3
42 48
0

2.out
7

#include<stdio.h> #include<string.h> #define MAXN 101 #define MAXE 20001 struct Edge{     int v;     Edge *next; } *edge[MAXN],mempool[MAXE]; int flag,n,snum,memnum,stack[MAXN],dfn[MAXN], low[MAXN],vis[MAXN],app[MAXN],ans; inline int min(int a, int b){     return a<b?a:b; } void add(int u, int v){     Edge *e=&mempool[memnum++];     e->v=v,e->next=edge[u],edge[u]=e; } int getn(){     int res=0;char ch;     for(ch=getchar();'0'<=ch&&ch<='9';ch=getchar())         res=res*10+ch-'0';     if(ch=='\n') flag=1;     return res; } void dfs(int now, int f){     stack[++snum]=now;     low[now]=dfn[now]=snum;     vis[now]=1;     int c=0;     for(Edge *i=edge[now];i;i=i->next){         if(i->v!=f){             if(vis[i->v]){                 low[now]=min(low[now],dfn[i->v]);             }else{                 ++c;                 dfs(i->v,now);                 low[now]=min(low[now],low[i->v]);                 if(f&&low[i->v]>=dfn[now]&&!app[now]){                     ++ans;                     app[now]=1;                 }             }         }     }     if(!f&&c>1&&!app[now]) ++ans; } void init(){     memnum=0;     ans=0;     snum=0;     memset(edge,0,sizeof(edge));     memset(app,0,sizeof(app));     memset(vis,0,sizeof(vis));     memset(dfn,0,sizeof(dfn));     memset(low,0,sizeof(low)); } int main(){     int now,t;     while(scanf("%d\n",&n)!=EOF){         if(!n) break;         init();         while(now=getn()){             if(!now) break;             flag=0;             while(t=getn()){                 add(now,t);                 add(t,now);                 if(flag) break;             }         }         if(n<=2) printf("0\n");         else{             dfs(1,0);             printf("%d\n",ans);         }     }     return 0; }
Categories: OI Tags: , , ,
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: