主要思路:使用tarjan选取一个根节点建立一个棵搜索树,判断一个点是割点的充分必要条件是,对于一个节点u如果他的孩子节点v的low值大于等于u的出生日期dfn值,进行下一步判断,如果u是我们选的根节点,我们还需要判断一下他的孩子节点的个数是否大于一,如果大于一则他是割点,反之不是。如果u不是根节点,那他就是割点了。因为我是第一次接触targin算法,跟着学姐的课件和自己的感觉敲了下去,WA已经刷屏了,原因就是我错误的认为根节点只要度数大于一就可以(学姐课件上就是先写的这个啊T T),其实是他也必须要满足low >= dfn的关系。。。好吧,以后记住就可以了^ ^.
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int maps[110][110],dfn[110],low[110],tot,n,root_son,mark[110],flag[110]; char a[300]; void tarjan(int u,int fa) { for(int i = 1; i <= n; i++) { if(maps[u][i]) { ///cout<<"the fa = "<<u<<" the son is = "<<i<<endl; if(!flag[i]) { flag[i] = 1; /// cout<<"the son "<<i<<" is not visited "; dfn[i] = low[i] = ++tot; tarjan(i,u); low[u] = min(low[i],low[u]); if(low[i] >= dfn[u]) { if(u != 1) mark[u] = 1; else root_son++; } } else if(i != fa) { ///cout<<"the son "<<i<<" is visited"<<endl; low[u] = min(low[u],dfn[i]); /// cout<<"low["<<u<<"]"<<" hes become "<<low[u]<<endl; } } } } int main() { //freopen("in.txt","r",stdin); while(~scanf("%d",&n) && n) { getchar(); memset(maps,0,sizeof(maps)); while(gets(a)) { if(a[0] == '0') break; int len = strlen(a); a[len] = ' '; a[len+1] = '