POJ—1144 电话网络
题目描述
输入输出
输入样例
5 5 1 2 3 4 0 6 2 1 3 5 4 6 2 0 0
输出样例
1 2
题意分析
题中的电话交换机就是图中的点,线路双向说明是个无向图.题中至关重要的点也就是图中的割点,一旦出现了问题影响的点也就会有许多个.所以这个题主要是求割点的个数.直接上Tarjan算法,注意输入格式的控制比较特殊.
参考代码
#include<iostream> #include<set> #include<string.h> using namespace std; const int maxn = 100 + 10; int head[maxn],cnt,root; set<int> s; struct edge{ int to,next; }e[maxn*maxn]; int low[maxn],dfn[maxn],num; void add(int u,int v){ e[++cnt].next = head[u]; e[cnt].to = v; head[u] = cnt; } void tarjan(int u,int fa){ dfn[u] = low[u]=++num; int count = 0; for(int i = head[u]; i;i=e[i].next){ int v = e[i].to; if(fa==v){ continue; } if(!dfn[v]){ tarjan(v,u); low[u] = min(low[u],low[v]); if(low[v]>=dfn[u]){ count++; if(u!=root || count > 1){ s.insert(u);//这里不能使用一个变量做统计,因为可能会出现判断重复的情况,可以使用一个结合,把成立的点加进去,最后统计集合大小即可. } } }else{ low[u] = min(low[u],low[v]); } } } void init(){ memset(head,0,sizeof(head)); memset(low,0,sizeof(low)); memset(dfn,0,sizeof(dfn)); cnt = num = 0; s.clear(); } int main() { int n,u,v; while(cin>>n&&n){//控制每个case init(); while(cin>>u&&u){ while(1){ char ch = getchar(); if(ch=='\n'){ break; } cin>>v; add(u,v); add(v,u); } } for(int i = 1; i <= n; i++){ if(!dfn[i]){ root = i; tarjan(i,0); } } cout<<s.size()<<endl; } return 0; }
