LA 7272 Promotions（dfs）

https://vjudge.net/problem/UVALive-7272

题意：

公司要提拔人，现在有n个人，现在有m条有向边，A->B表示A的表现比B好，也就是如果B晋升了，那么A肯定会晋升。

现在给出【L，R】，计算出晋升L个人时肯定会晋升的人数，晋升R个人时肯定会晋升的人数，还有肯定不可能晋升的人数。

思路：

先说一下计算不可能人数的算法。

这个需要反向建图，我们dfs遍历，假设现在从第i个人开始遍历，遍历得到它的子节点的个数，这就是说如果i晋升的话，他前面的人也都必须要晋升。

如果这个人数大于了限定的晋升人数，那么这个人肯定是不可能晋升的。

剩余两个也是这样分析的，具体参见代码。

 #include<iostream>

 #include<string>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 #include<cstdio>

 using namespace std;

 const int maxn=+;

 int n, m;

 int A,B;

 int num;

 vector<int> g[maxn];

 vector<int> r_g[maxn];

 int vis[maxn];

 void r_dfs (int u)

 {

     if(vis[u])  return;

     vis[u]=;

     num++;

     for(int i=;i<r_g[u].size();i++)

     {

         r_dfs(r_g[u][i]);

     }

 }

 void dfs (int u)

 {

     if(vis[u])  return;

     vis[u]=;

     num++;

     for(int i=;i<g[u].size();i++)

     {

         dfs(g[u][i]);

     }

 }

 int main()

 {

     //freopen("D:\\input.txt", "r", stdin);

     while (~scanf("%d%d%d%d",&A, &B, &n, &m))

     {

         for(int i=;i<n;i++)  {g[i].clear();r_g[i].clear();}

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

         {

             int u,v;

             scanf("%d%d",&u,&v);

             g[u].push_back(v);

             r_g[v].push_back(u);

         }

         int ans1=,ans2=,ans3=;

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

         {

             memset(vis,,sizeof(vis));

             num=-;

             r_dfs(i);

             if(num>=B)  ans3++;

             memset(vis,,sizeof(vis));

             num=-;

             dfs(i);

             if(num>=n-A)  ans1++;

             if(num>=n-B)  ans2++;

         }

         printf("%d\n%d\n%d\n",ans1,ans2,ans3);

     }

     return ;

 }