poj - 2186 Popular Cows && poj - 2553 The Bottom of a Graph (强连通)-白红宇

poj - 2186 Popular Cows && poj - 2553 The Bottom of a Graph (强连通)

阅读量：5099 次

发布时间：2019-06-13

本文共 6385 字，大约阅读时间需要 21 分钟。

http://poj.org/problem?id=2186

给定n头牛,m个关系,每个关系a,b表示a认为b是受欢迎的,但是不代表b认为a是受欢迎的,关系之间还有传递性,假如a->b,b->c 则a->c,问有多少头牛被其他所有的牛欢迎.

统计出度为0的点,如果不为1,则表示不存在这样的牛,为1的话就输出这个集合点的数量.

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 #include 
        
           5 #include 
         
            6 #include 
          
            7 #include 
           
             8 #include 
            
              9 #include 
             
               10 #include 
              
                11 #include 
               
                 12 #include 
                
                  13 #include 
                  14 #include 
                  
                    15 16 #define CL(arr, val) memset(arr, val, sizeof(arr)) 17 18 #define ll long long 19 #define inf 0x7f7f7f7f 20 #define lc l,m,rt<<1 21 #define rc m + 1,r,rt<<1|1 22 #define pi acos(-1.0) 23 24 #define L(x) (x) << 1 25 #define R(x) (x) << 1 | 1 26 #define MID(l, r) (l + r) >> 1 27 #define Min(x, y) (x) < (y) ? (x) : (y) 28 #define Max(x, y) (x) < (y) ? (y) : (x) 29 #define E(x) (1 << (x)) 30 #define iabs(x) (x) < 0 ? -(x) : (x) 31 #define OUT(x) printf("%I64d\n", x) 32 #define lowbit(x) (x)&(-x) 33 #define Read() freopen("a.txt", "r", stdin) 34 #define Write() freopen("dout.txt", "w", stdout); 35 36 using namespace std; 37 #define N 10100 38 //N为最大点数 39 #define M 50100 40 //M为最大边数 41 int n, m;//n m 为点数和边数 42 43 struct Edge{ 44 int from, to, nex; 45 bool sign;//是否为桥 46 }edge[M<<1]; 47 int head[N], edgenum; 48 void add(int u, int v){ //边的起点和终点 49 Edge E={u, v, head[u], false}; 50 edge[edgenum] = E; 51 head[u] = edgenum++; 52 } 53 54 int DFN[N], Low[N], Stack[N], top, Time; //Low[u]是点集{u点及以u点为根的子树} 中(所有反向弧)能指向的(离根最近的祖先v) 的DFN[v]值(即v点时间戳) 55 int taj;//连通分支标号，从1开始 56 int Belong[N];//Belong[i] 表示i点属于的连通分支 57 bool Instack[N]; 58 vector
                   
                     bcc[N]; //标号从1开始 59 60 void tarjan(int u ,int fa){ 61 DFN[u] = Low[u] = ++ Time ; 62 Stack[top ++ ] = u ; 63 Instack[u] = 1 ; 64 65 for (int i = head[u] ; ~i ; i = edge[i].nex ){ 66 int v = edge[i].to ; 67 if(DFN[v] == -1) 68 { 69 tarjan(v , u) ; 70 Low[u] = min(Low[u] ,Low[v]) ; 71 if(DFN[u] < Low[v]) 72 { 73 edge[i].sign = 1;//为割桥 74 } 75 } 76 else if(Instack[v]) Low[u] = min(Low[u] ,DFN[v]) ; 77 } 78 if(Low[u] == DFN[u]){ 79 int now; 80 taj ++ ; bcc[taj].clear(); 81 do{ 82 now = Stack[-- top] ; 83 Instack[now] = 0 ; 84 Belong [now] = taj ; 85 bcc[taj].push_back(now); 86 }while(now != u) ; 87 } 88 } 89 90 void tarjan_init(int all){ 91 memset(DFN, -1, sizeof(DFN)); 92 memset(Instack, 0, sizeof(Instack)); 93 top = Time = taj = 0; 94 for(int i=1;i<=all;i++)if(DFN[i]==-1 )tarjan(i, i); //注意开始点标！！！ 95 } 96 vector
                    
                     G[N]; 97 int du[N]; 98 void suodian(){ 99 memset(du, 0, sizeof(du));100 for(int i = 1; i <= taj; i++)G[i].clear();101 for(int i = 0; i < edgenum; i++){102 int u = Belong[edge[i].from], v = Belong[edge[i].to];103 if(u!=v)104 {105 G[u].push_back(v), du[u]++;106 // printf("%d %d\n",u,v);107 }108 }109 }110 void init(){memset(head, -1, sizeof(head)); edgenum=0;}111 int main()112 {113 //Read();114 int a,b;115 while(~scanf("%d%d",&n,&m))116 {117 init();118 //scanf("%d%d",&n,&m);119 for(int i=0;i

http://poj.org/problem?id=2553

开始题意理解不了,看了discuss,题意是说:

题目的意思是，sink中的点v如果能到w点，那么w点也必须能到v点，所以是所有出度为0的连通分量的点.

因为能互相到达的必在同一个连通分量.

依次判断1—n的点是不是出度为0的点,保存输出即可.

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 #include 
        
           5 #include 
         
            6 #include 
          
            7 #include 
           
             8 #include 
            
              9 #include 
             
               10 #include 
              
                11 #include 
               
                 12 #include 
                
                  13 #include 
                  14 #include 
                  
                    15 16 #define CL(arr, val) memset(arr, val, sizeof(arr)) 17 18 #define ll long long 19 #define inf 0x7f7f7f7f 20 #define lc l,m,rt<<1 21 #define rc m + 1,r,rt<<1|1 22 #define pi acos(-1.0) 23 24 #define L(x) (x) << 1 25 #define R(x) (x) << 1 | 1 26 #define MID(l, r) (l + r) >> 1 27 #define Min(x, y) (x) < (y) ? (x) : (y) 28 #define Max(x, y) (x) < (y) ? (y) : (x) 29 #define E(x) (1 << (x)) 30 #define iabs(x) (x) < 0 ? -(x) : (x) 31 #define OUT(x) printf("%I64d\n", x) 32 #define lowbit(x) (x)&(-x) 33 #define Read() freopen("a.txt", "r", stdin) 34 #define Write() freopen("dout.txt", "w", stdout); 35 36 using namespace std; 37 #define N 5100 38 //N为最大点数 39 #define M 150100 40 //M为最大边数 41 int n, m;//n m 为点数和边数 42 43 struct Edge{ 44 int from, to, nex; 45 bool sign;//是否为桥 46 }edge[M<<1]; 47 int head[N], edgenum; 48 void add(int u, int v){ //边的起点和终点 49 Edge E={u, v, head[u], false}; 50 edge[edgenum] = E; 51 head[u] = edgenum++; 52 } 53 //DNF[i]表示遍历到第i点时,是第几次dfs 54 //Low[u] 表示 以u点为父节点的 子树 能连接到 [栈中] 最上端的点 的DFN值(换句话说，是最小的DFN，因为最上端的DFN是最小的嘛） 55 int DFN[N], Low[N], Stack[N], top, Time; //Low[u]是点集{u点及以u点为根的子树} 中(所有反向弧)能指向的(离根最近的祖先v) 的DFN[v]值(即v点时间戳) 56 int taj;//连通分支标号，从1开始 57 int Belong[N];//Belong[i] 表示i点属于的连通分支 58 bool Instack[N],flag; 59 vector
                   
                     bcc[N]; //标号从1开始 60 61 void tarjan(int u ,int fa){ 62 DFN[u] = Low[u] = ++ Time ; 63 Stack[top ++ ] = u ; 64 Instack[u] = 1 ; 65 66 for (int i = head[u] ; ~i ; i = edge[i].nex ){ 67 int v = edge[i].to ; 68 if(DFN[v] == -1) 69 { 70 tarjan(v , u) ; 71 Low[u] = min(Low[u] ,Low[v]) ; 72 if(DFN[u] < Low[v]) 73 { 74 edge[i].sign = 1;//为割桥 75 } 76 } 77 else if(Instack[v]) 78 { 79 Low[u] = min(Low[u] ,DFN[v]) ; 80 if(DFN[v]!=Low[v]) flag=1; //父节点还不是根节点 81 } 82 } 83 if(Low[u] == DFN[u]){ 84 int now; 85 taj ++ ; bcc[taj].clear(); 86 do{ 87 now = Stack[-- top] ; 88 Instack[now] = 0 ; 89 if(Belong[now]!=-1) flag=1; //每个节点都要只属于同一个联通分量 90 Belong [now] = taj ; 91 bcc[taj].push_back(now); 92 }while(now != u) ; 93 } 94 } 95 96 void tarjan_init(int all){ 97 memset(DFN, -1, sizeof(DFN)); 98 memset(Instack, 0, sizeof(Instack)); 99 memset(Belong,-1,sizeof(Belong));100 top = Time = taj = 0;101 for(int i=1;i<=all;i++)if(DFN[i]==-1 )tarjan(i, i); //注意开始点标！！！102 }103 vector
                    
                     G[N];104 int du[N];105 void suodian(){106 memset(du, 0, sizeof(du));107 for(int i = 1; i <= taj; i++)G[i].clear();108 for(int i = 0; i < edgenum; i++){109 int u = Belong[edge[i].from], v = Belong[edge[i].to];110 if(u!=v)111 {112 G[u].push_back(v), du[u]++;113 // printf("%d %d\n",u,v);114 }115 }116 }117 void init(){memset(head, -1, sizeof(head)); edgenum=0;}118 int p[N];119 int main()120 {121 //Read();122 int a,b;123 while(~scanf("%d",&n)&&n)124 {125 scanf("%d",&m);126 init();127 flag=0;128 while(m--)129 {130 scanf("%d%d",&a,&b);131 add(a,b);132 }133 tarjan_init(n);134 suodian();135 int j=0;136 for(int i=1;i<=n;i++)137 {138 if(du[Belong[i]]==0)139 p[j++]=i;140 }141 // printf("%d\n",j);142 if(j==0) {printf("\n");continue;}143 for(int i=0;i