题目链接: 传送门 https://loj.ac/problem/10100
思路:
就是求割点的个数, 直接 Tarjan 算法就行.
注意输入格式 (判断比较水).
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #include<vector>
- #include<string>
- #include<stack>
- #include<algorithm>
- using namespace std;
- const int maxn = 550;
- int num[maxn],low[maxn],vis[maxn],gedian[maxn],tim,cnt,root;
- vector <int> vc[maxn];
- int MIN(int x,int y)
- {
- return x<y?x:y;
- }
- void Init()
- {
- memset(num,0,sizeof(num));
- memset(low,0,sizeof(low));
- memset(vis,0,sizeof(vis));
- memset(gedian,0,sizeof(gedian));
- for(int i=0;i<maxn;i++) vc[i].clear();
- tim=0;cnt=0;
- }
- void Tarjan(int u,int pre)
- {
- low[u]=num[u]=++tim;
- vis[u]=1;
- int v,i,tt=0;
- for(i=0;i<vc[u].size();i++){
- v=vc[u][i];
- if(!vis[v]){
- tt++;
- Tarjan(v,u);
- low[u]=MIN(low[u],low[v]);
- if((u==root&&tt>1)||(u!=root&&num[u]<=low[v])) gedian[u]=1;
- }
- else low[u]=MIN(low[u],num[v]);
- }
- }
- int main(void)
- {
- int n,m,i,j,x,y;
- char ch;
- string str;
- while(~scanf("%d",&n)&&n){
- Init();
- int c1=0,c2;
- while(scanf("%d",&x)&&x){
- if(c1>=n) break;c1++;
- c2=0;
- while(1){
- c2++;
- scanf("%d",&y);
- vc[x].push_back(y);
- vc[y].push_back(x);
- if(c2>=n) break;
- ch=getchar();
- if(ch=='\n') break;
- }
- }
- for(i=1;i<=n;i++)
- if(vis[i]==0){
- root=i;
- Tarjan(i,-1);
- }
- for(i=1;i<=n;i++)
- if(gedian[i]==1) cnt++;
- printf("%d\n",cnt);
- }
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-2949344.html