ZOJ1311(Network)

题目大意:给你一副无向图，求有多少个割点
题目思路:tarjan算法（此题读入是字符串读入，需注意）
  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstdlib>
  4 #include <cmath>
  5 #include <algorithm>
  6 #include <cstring>
  7 #include <stack>
  8 #include <cctype>
  9 #include <queue>
 10 #include <string>
 11 #include <vector>
 12 #include <set>
 13 #include <map>
 14 #include <climits>
 15 #define lson root<<1,l,mid
 16 #define rson root<<1|1,mid+1,r
 17 #define fi first
 18 #define se second
 19 #define ping(x,y) ((x-y)*(x-y))
 20 #define mst(x,y) memset(x,y,sizeof(x))
 21 #define mcp(x,y) memcpy(x,y,sizeof(y))
 22 #define Min(x,y) (x<y?x:y)
 23 #define Max(x,y) (x>y?x:y)
 24 using namespace std;
 25 #define gamma 0.5772156649015328606065120
 26 #define MOD 1000000007
 27 #define inf 0x3f3f3f3f
 28 #define N 10005
 29 #define maxn 1000050
 30 typedef long long LL;
 31 typedef pair<int,int> PII;
 32 
 33 int n,m,ans,son;
 34 int pic[150][150];
 35 int low[150],vis[150],area[150];
 36 int dfn[150],deep;
 37 
 38 inline void init(){
 39     mst(area,0);
 40     mst(vis,0);
 41     mst(pic,0);
 42     ans=son=0;
 43     deep=1;
 44     low[1]=dfn[1]=1;
 45     vis[1]=1;
 46 }
 47 
 48 void dfs(int x){
 49    for(int i=1;i<=n;++i)
 50     if(pic[x][i]){
 51         if(vis[i]){low[x]=min(low[x],dfn[i]);}
 52         else{
 53             vis[i]=1;
 54             low[i]=dfn[i]=++deep;
 55             dfs(i);
 56             low[x]=min(low[x],low[i]);
 57             if(low[i]>=dfn[x]){
 58                 if(x==1)++son;
 59                 else ++area[x];
 60             }
 61         }
 62     }
 63 }
 64 
 65 void read(){
 66     char str[1000];
 67     while(gets(str)){
 68         if(!strcmp("0",str))break;
 69         int len=strlen(str);
 70         int i=0,temp=0;
 71         while(str[i]==' ')++i;
 72         while(isdigit(str[i])){
 73             temp=temp*10+str[i]-'0';
 74             ++i;
 75         }
 76         int x=temp;
 77         while(i<len){
 78             temp=0;
 79             while(str[i]==' ')++i;
 80             while(isdigit(str[i])){
 81                 temp=temp*10+str[i]-'0';
 82                 ++i;
 83             }
 84             pic[x][temp]=pic[temp][x]=1;
 85         }
 86     }
 87 }
 88 
 89 int main(){
 90     int i,j,group,Case=0,x,y;
 91     while(scanf("%d",&n)!=EOF&&n){
 92         getchar();
 93         init();
 94         read();
 95         dfs(1);
 96         if(son>1)++ans;
 97         for(i=1;i<=n;++i)
 98             if(area[i])
 99                 ++ans;
100         printf("%d
",ans);
101     }
102     return 0;
103 }