poj 1236+hdu2767 有向图缩点+看度数（tarjan）

1236题意：一个有向图，1，求至少从几个点出发可以遍历该图，2:，求至少添加多少边，使强连通。而，HDU的只有后面一问。

解;先缩点，第一问只需找所有入度为0的点即可。，第2问，max（入度为0的点，出度为0点）。也写了2个小时。。虽然1A，但是因为细节卡了，不应该。

代码详细说：

#include<iostream>   //0ms 1A poj1236

#include<vector>

#include<cstdio>

#include<cstring>

#include<stack>

using namespace std;

int n;

vector<vector<int> >edges(101);

int visited[101];

int low[101];

int dfn[101];

int ind[101];int outd[101];          //统计出入度

int Strongly_connected_branch[101];  //并为一个强连通，标记为1.2.3...

int num;int times;

stack<int>s;

bool instack[101];

void tarjan(int u)               //dfs

{

    low[u]=dfn[u]=times++;

    instack[u]=1;

    s.push(u);

    int len=edges[u].size();

    for(int i=0;i<len;i++)

    {

        int v=edges[u][i];

        if(visited[v]==0)          //小心细节！

        {

             visited[v]=1;

               tarjan(v);

            if(low[u]>low[v])low[u]=low[v];

        }

        else if(instack[v]&&low[u]>dfn[v])     //有向图，要问是否在栈中，后向边，V为U某个祖先

        {

            low[u]=dfn[v];

        }

    }

    if(dfn[u]==low[u])         //在一个SCC

    {

        num++;int temp;

         do

        {

             temp=s.top();

             instack[temp]=0;

            s.pop();

            Strongly_connected_branch[temp]=num;

        } while(temp!=u);

    }

}

void readin()            //读入数据

{

    scanf("%d",&n);

    int to;

    for(int i=1;i<=n;i++)

    {

        scanf("%d",&to);

        while(to!=0)

       {

           edges[i].push_back(to);

           scanf("%d",&to);

       }

    }

}

int ind0,outd0;

void initialize()             //初始化

{

    ind0=outd0=num=times=0;

}

void solve()

{

    for(int i=1;i<=n;i++)        //原图未必连通

       if(visited[i]==0)

        {

            visited[i]=1;

            tarjan(i);

        }

     for(int i=1;i<=n;i++)     //自己思得：枚举所有边，在不同scc中的，这样统计其出入度，缩点只是把所有SCC分开

   {                           //这样统计，出入度为0的肯定没问题，但是是收缩后的图（原图中有几条边SCC间连任连几条）的出入度，

      int len=edges[i].size();

       for(int j=0;j<len;j++)

       {

          int v=edges[i][j];

          if(Strongly_connected_branch[v]!=Strongly_connected_branch[i])

          {

            outd[Strongly_connected_branch[i]]++;

            ind[Strongly_connected_branch[v]]++;

          }

       }

    }

    for(int i=1;i<=num;i++)

    {

        //cout<<"out:"<<outd[i]<<"in:"<<ind[i]<<endl;

       if(outd[i]==0)outd0++;

       if(ind[i]==0)ind0++;

    }

}

int main()

{

   readin();

   initialize();

   solve();

   int max0=outd0;

   if(num==1){printf("1\n0\n");return 0 ;}        //如果原来就强连通，特判

   if(ind0>max0)max0=ind0;

   printf("%d\n%d\n",ind0,max0);

   return 0;

}

#include<iostream>   //hdu 260ms

#include<vector>

#include<cstdio>

#include<cstring>

#include<stack>

using namespace std;

int n;int m;

vector<vector<int> >edges(20001);

int visited[20001];

int low[20001];

int dfn[20001];

int ind[20001];int outd[20001];          //统计出入度

int Strongly_connected_branch[20001];  //并为一个强连通，标记为1.2.3...

int num;int times;

stack<int>s;

bool instack[20001];

void tarjan(int u)

{

    low[u]=dfn[u]=times++;

    instack[u]=1;

    s.push(u);

    int len=edges[u].size();

    for(int i=0;i<len;i++)

    {

        int v=edges[u][i];

        if(visited[v]==0)

        {

             visited[v]=1;

               tarjan(v);

            if(low[u]>low[v])low[u]=low[v];

        }

        else if(instack[v]&&low[u]>dfn[v])     //有向图，要问是否在栈中，后向边，V为U某个祖先

        {

            low[u]=dfn[v];

        }

    }

    if(dfn[u]==low[u])         //在一个SCC

    {

        num++;int temp;

         do

        {

             temp=s.top();

             instack[temp]=0;

            s.pop();

            Strongly_connected_branch[temp]=num;

        } while(temp!=u);

    }

}

void readin()

{

    scanf("%d%d",&n,&m);

    int from,to;

    for(int i=1;i<=m;i++)

    {

        scanf("%d%d",&from,&to);

        edges[from].push_back(to);

    }

}

int ind0,outd0;

void initialize()              //多组数据，必需初始化

{

    ind0=outd0=num=times=0;

    for(int i=0;i<=n;i++)

    {

        instack[i]=low[i]=dfn[i]=visited[i]=ind[i]=outd[i]=0;

        edges[i].clear();

        Strongly_connected_branch[i]=-1;

    }

}

void solve()

{

    for(int i=1;i<=n;i++)

       if(visited[i]==0)

        {

            visited[i]=1;

            tarjan(i);

        }

     for(int i=1;i<=n;i++)     //自己思得：枚举所有边，在不同scc中的，这样统计其出入度，缩点只是把所有SCC分开

   {                           //这样统计，出入度为0的肯定没问题，但是是收缩后的图（原图中有几条边SCC间连任连几条）的出入度，

      int len=edges[i].size();

       for(int j=0;j<len;j++)

       {

          int v=edges[i][j];

          if(Strongly_connected_branch[v]!=Strongly_connected_branch[i])

          {

            outd[Strongly_connected_branch[i]]++;

            ind[Strongly_connected_branch[v]]++;

          }

       }

    }

    for(int i=1;i<=num;i++)

    {

       if(outd[i]==0)outd0++;

       if(ind[i]==0)ind0++;

    }

}

int main()

{

    int tcase;

    scanf("%d",&tcase);

   while(tcase--)

   {

       initialize();

       readin();

       solve();

     int max0=outd0;

   if(num==1){printf("0\n");continue;}

   if(ind0>max0)max0=ind0;

   printf("%d\n",max0);

   }

   return 0;

}

巴特西

poj 1236+hdu2767 有向图缩点+看度数（tarjan）

最新文章

热门文章

巴特西

poj 1236+hdu2767 有向图 缩点+看度数（tarjan）

最新文章

热门文章

poj 1236+hdu2767 有向图缩点+看度数（tarjan）