poj1523赤裸裸的割点

2023-10-23 09:10

文章标签 割点赤裸裸 poj1523

本文主要是介绍poj1523赤裸裸的割点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这题真是没什么好说的。。。赤裸裸的求割点直接模板上

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<vector>
 5 #define maxn 1100
 6 
 7 using namespace std;
 8 
 9 vector<int> g[maxn];
10 int dfn[maxn],low[maxn];
11 int vis[maxn],cnt[maxn];
12 int k=1,f=0,index=0,m;
13 void dfs(int x)
14 {
15  //   cout<<"1"<<endl;
16     int c=0;
17     for(int i=0;i<g[x].size();i++)
18     {
19         int e=g[x][i];
20         if(vis[e]==0)
21         {
22             dfn[e]=low[e]=++index;
23             vis[e]=1;
24             dfs(e);
25             low[x]=min(low[e],low[x]);
26             if(low[e]>=dfn[x])
27             {
28                 cnt[x]++;
29             }
30         }
31         else low[x]=min(low[x],dfn[e]);
32     }
33 }
34 void solve()
35 {
36     f=index=0;
37     memset(dfn,0,sizeof(dfn));
38     memset(cnt,0,sizeof(cnt));
39     memset(vis,0,sizeof(vis));
40     memset(low,0,sizeof(low));
41     printf("Network #%d\n",k++);
42     vis[1]=1;
43     dfn[1]=low[1]=++index;
44     dfs(1);
45     if(cnt[1]>=1) cnt[1]--;
46     for(int i=1;i<=m;i++)
47     {
48         if(cnt[i])
49         {
50             printf("  SPF node %d leaves %d subnets\n",i,cnt[i]+1);
51             f=1;
52         }
53     }
54     if(f==0) printf("  No SPF nodes\n");
55     printf("\n");
56 }
57 int main()
58 {
59     int a,b;
60     while(scanf("%d",&a)!=EOF)
61     {
62         for(int i=1;i<=maxn;i++)
63             g[i].clear();
64         if(a==0) break;
65         scanf("%d",&b);
66         g[a].push_back(b);
67         g[b].push_back(a);
68         m=a<b?b:a;
69         while(1)
70         {
71              int x,y;
72              scanf("%d",&x);
73              if(x==0) break;
74              scanf("%d",&y);
75              g[x].push_back(y);
76              g[y].push_back(x);
77              m=m>x?m:x;
78              m=m>y?m:y;
79         }
80         solve();
81     }
82     return 0;
83 }