poj2186 求有向图G中所有点都能到达的点的数量

/*题意：有向图，求这样的点的数量：所有点都能到达它.缩点成有向无环图，思：如果该强连通有出度，那么

从该出度出去的边必然回不来（已经缩点了），所以有出度的强连通必然不是。那么是不是所有出度为0的强连通

分量都是呢？显然不是，如果存在多个出度为0的强连通，他们必然无解（他们之间必然不连通）。

任然遍历边，判断不在一个连通分量中的边（即为缩点后的边）和点，考察期出度即可。*/

#include<iostream>     //329ms，1A，基础题。

#include<vector>

#include<cstdio>

#include<cstring>

#include<stack>

#include<queue>

using namespace std;

int n;int m;

const int MAX=10001;

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

int visited[MAX];

int low[MAX];

int dfn[MAX];

bool has_outd[MAX];        //是否有出度

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

int num;int times;

bool is_popular[MAX];       //整个强连通分支i是否有出度，其中一个点有即有

stack<int>s;

bool instack[MAX];

int num_of_popular;          //统计最终数量

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 initialize()          //初始化

{

    num_of_popular=num=times=0;

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

    {

        has_outd[i]=instack[i]=low[i]=dfn[i]=visited[i]=0;

        edges[i].clear();

        is_popular[i]=1;

        Strongly_connected_branch[i]=-1;

    }

}

bool readin()

{

    scanf("%d",&n);

    scanf("%d",&m);

    initialize();

    int from,to;

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

    {

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

        edges[from].push_back(to);

    }

    return 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分开

   {

      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])//不在用一个强连通分支

          {

            has_outd[i]=1;                  //i所在强连通分量有出度

            is_popular[Strongly_connected_branch[i]]=0; //其所在强连通全跪！

            break;

          }

       }

    }

    queue<int>q;

    for(int i=1;i<=n;i++)          //统计期所在强连通出度为0的点

    {

       if(is_popular[Strongly_connected_branch[i]]==0){continue;}

       if(has_outd[i]==0)q.push(i);

    }

    int te=Strongly_connected_branch[q.front()];

    while(!q.empty())           //判断他们是否都在一个强连通中，否则跳出，无解。

    {

        int cur=q.front();

        if(te!=Strongly_connected_branch[cur]){printf("0\n");return;}

        num_of_popular++;

        q.pop();

        te=Strongly_connected_branch[cur];

    }

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

}

int main()

{

      readin();

       solve();

   return 0;

}
巴特西

poj2186 求有向图G中所有点都能到达的点的数量

最新文章

热门文章
