Codeforces Round #503 (by SIS, Div. 2)B 1020B Badge （拓扑）-白红宇

Codeforces Round #503 (by SIS, Div. 2)B 1020B Badge （拓扑）

阅读量：6692 次

发布时间：2019-06-25

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

题目大意：每个同学可以指定一个人，然后构成一个有向图。1-n次查询，从某个人开始并放入一个东西，然后循环，直到碰到一个人已经放过了，就输出。

思路：直接模拟就可以了，O(n^2) 但是O(n)也可以实现，不是太懂大神的思路。

初始化ans[i] = i, 一个点能被输出的话就是 ans[i] = i (可以模拟一下)，这个ans是如何算的呢。大神用了topo排序。记录入度数，然后把入读为0放入队列，取出来然后连接点入度--， ans[i] = p[i] ( p[i] 是 i 指定的人 )直到队列为空。

O(n^2)代码：

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 using namespace std;15 #define mem(a,b) memset((a),(b),sizeof(a))16 #define mp make_pair17 #define pb push_back18 #define fi first19 #define se second20 #define sz(x) (int)x.size()21 #define all(x) x.begin(),x.end()22 typedef long long ll;23 const int inf = 0x3f3f3f3f;24 const ll INF =0x3f3f3f3f3f3f3f3f;25 const double pi = acos(-1.0);26 const double eps = 1e-5;27 const ll mod = 1e9+7;28 //head29 bool vis[1000 + 10];30 vector
                  
                    G[1000 + 10];31 int main() {32 int n, x;33 scanf("%d", &n);34 for(int i = 1; i <= n; i++) {35 scanf("%d", &x);36 G[i].push_back(x);37 }38 for(int i = 1; i <= n; i++) {39 mem(vis, false);40 vis[i] = true;41 int net = G[i][0];42 while(vis[net] != true) {43 vis[net] = true;44 net = G[net][0];45 }46 printf("%d ", net);47 }48 }

O(n)代码：

1 #include
     
       2 #include
      
        3 using namespace std; 4 const int maxn = 1000 + 10; 5 int p[maxn], ans[maxn], deg[maxn]; 6  7 int res(int i) {
   //比较神奇 也就是循环 8     return i == ans[i] ? i : res(p[i]); 9 }10 11 int main(int argc, char const *argv[])12 {13     int n;14     scanf("%d", &n);15     for(int i = 1; i <= n; i++) {16         scanf("%d", &p[i]);//每个点指定的点17         deg[p[i]]++;//入读++18     }19     queue
       
         q;20     for(int i = 1; i <= n; i++) {
   //初始化ans21         ans[i] = i;22         if(deg[i] == 0)//入度为0 进队列23             q.push(i);24     }25     while(!q.empty()){
   //topo26         int u = q.front(); q.pop();27         deg[p[u]]--;28         ans[u] = p[u];//这里不是太懂(模拟一下比较好)29         if(deg[p[u]] == 0)30             q.push(p[u]);31     }32     for(int i = 1; i <= n; i++)33         printf("%d ", res(i));34     return 0;35 }

转载于:https://www.cnblogs.com/ACMerszl/p/9572927.html

你可能感兴趣的文章