fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. const ll INF = 1e9;
  6. const int N = 1e4+10;
  7.  
  8. vector<int>dir[N],v[N],con[N];
  9. bool visited[N],rec[N],vis[N];
  10. int sz,sum[N],a[N];
  11.  
  12.  
  13. void dfs2(int s){
  14.     vis[s]=true;
  15.     int sol=-INF;
  16.     for(int i=0;i<dir[s].size();i++){
  17.         if(!vis[dir[s][i]])dfs2(dir[s][i]);
  18.         sol=max(sol,sum[dir[s][i]]+1);
  19.     }
  20.     sum[s]=sol;
  21. }
  22.  
  23. void dfs(int s){
  24.     con[sz].push_back(s);
  25.     vis[s]=true;
  26.     for(int i=0;i<v[s].size();i++){
  27.         if(!vis[v[s][i]])dfs(v[s][i]);
  28.     }
  29. }
  30.  
  31. bool ccc(int k){
  32.     if(!visited[k]){
  33.         visited[k]=true;
  34.         rec[k]=true;
  35.         for(int i=0;i<(int)dir[k].size();i++){
  36.             int p=dir[k][i];
  37.             if(!visited[p]&&ccc(p))return true;
  38.             else if(rec[p])return true;
  39.         }
  40.     }
  41.     rec[k]=false;
  42.     return false;
  43. }
  44.  
  45. bool cycle(){
  46.     for(int i=0;i<N;i++){
  47.         if(ccc(i))return true;
  48.     }
  49.     return false;
  50. }
  51.  
  52. int main()
  53. {
  54.     ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  55.     int t;
  56.     cin>>t;
  57.     while(t--){
  58.         int n,m,l,r,z;
  59.         memset(vis,false,sizeof(vis));
  60.         memset(visited,false,sizeof(visited));
  61.         memset(rec,false,sizeof(rec));
  62.         for(int i=0;i<N;i++){
  63.             v[i].clear();
  64.             dir[i].clear();
  65.             con[i].clear();
  66.         }
  67.         for(int i=0;i<N;i++)sum[i]=-INF;
  68.         cin>>n>>m;
  69.         for(int i=1;i<=m;i++){
  70.             cin>>l>>r>>z;
  71.             if(z==1)dir[r].push_back(l-1);
  72.             else dir[l-1].push_back(r);
  73.             v[l-1].push_back(r);
  74.             v[r].push_back(l-1);
  75.         }
  76.         if(cycle()){
  77.             cout<<-1<<"\n";
  78.             continue;
  79.         }
  80.         sz=0;
  81.         for(int i=0;i<N;i++){
  82.             if(!vis[i]){
  83.                 sz++;
  84.                 dfs(i);
  85.             }
  86.         }
  87.         sum[0]=0;
  88.         for(int i=1;i<=sz;i++){
  89.  
  90.             for(int j=0;j<con[i].size();j++){
  91.                 int p=con[i][j];
  92.                 if(!dir[p].size()){
  93.                     sum[p]=0;
  94.                 }
  95.             }
  96.             for(int j=0;j<con[i].size();j++){
  97.                 int p=con[i][j];
  98.                 if(dir[p].size()){
  99.                     dfs2(p);
  100.                 }
  101.             }
  102.         }
  103.         for(int i=1;i<=n;i++)a[i]=sum[i]-sum[i-1];
  104.         cout<<1<<"\n";
  105.         for(int i=1;i<=n;i++)cout<<a[i]<<" ";
  106.         cout<<"\n";
  107.     }
  108.  
  109.  
  110.  
  111.     return 0;
  112. }
  113. /*
  114.  
  115. 1
  116. 3 3
  117. 1 3 1
  118. 1 2 -1
  119. 2 3 -1
  120.  
  121. */
  122.  
Success #stdin #stdout 0s 4500KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/f4HSoO
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!