您的位置: 首页  >  IT文章  >  hrbustoj 1494（原题UVA 315 Network） 解题报告 tarjan求割点

hrbustoj 1494（原题UVA 315 Network） 解题报告 tarjan求割点

分类: IT文章 • 2022-05-28 00:02:35

　　主要思路：使用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] = '

相关推荐