fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4.  
  5. vector<ll> adj[100001], topso;
  6. vector<pair<ll, ll>> extra;
  7. bool ghumakya[100001];
  8. ll parent[100001];
  9.  
  10. void init(ll n)
  11. {
  12.     for(ll i=0; i<n; i++)
  13.     {
  14.         adj[i].clear();
  15.         ghumakya[i]=false;
  16.         parent[i]=i;
  17.     }
  18.     extra.clear();
  19. }
  20.  
  21. void dfs(ll v)
  22. {
  23.     ghumakya[v]=true;
  24.     for(ll u:adj[v])
  25.         if(!ghumakya[u])
  26.             dfs(u);
  27.     topso.push_back(v);
  28. }
  29.  
  30. void sortkardebhai(ll n)
  31. {
  32.     for(ll i=0; i<100001; i++)
  33.         ghumakya[i]=false;
  34.     topso.clear();
  35.     for(ll i=0; i<n; i++)
  36.         if(!ghumakya[i])
  37.             dfs(i);
  38.     reverse(topso.begin(), topso.end());
  39. }
  40.  
  41. ll find_set(ll x)
  42. {
  43.     if(parent[x]==x)
  44.         return x;
  45.     return parent[x]=find_set(parent[x]);
  46. }
  47.  
  48. void union_set(ll a, ll b)
  49. {
  50.     ll x=find_set(a), y=find_set(b);
  51.     if(x!=y)
  52.     {
  53.         adj[a].push_back(b);
  54.         x=y;
  55.     }
  56.     else
  57.         extra.push_back(make_pair(a, b));
  58. }
  59.  
  60. int main()
  61. {
  62.     ios_base::sync_with_stdio(false);
  63. 	cin.tie(NULL);
  64. 	cout.tie(NULL);
  65. 	ll t;
  66. 	cin>>t;
  67. 	while(t--)
  68. 	{
  69. 	    ll n, m;
  70. 	    cin>>n>>m;
  71. 	    ll pehlekaun[n], andar[n];
  72. 	    bool flag=true;;
  73. 	    unordered_set<ll> baaplog[n];
  74. 	    init(n);
  75. 	    for(ll i=0; i<n; i++)
  76. 	    {
  77. 	        andar[i]=0;
  78. 	        baaplog[i].clear();
  79. 	    }
  80. 	    pair<ll, ll> edges[m];
  81. 	    for(ll i=0; i<m; i++)
  82. 	    {
  83. 	        cin>>edges[i].first>>edges[i].second;
  84. 	        edges[i].first--;
  85. 	        edges[i].second--;
  86. 	        union_set(edges[i].first, edges[i].second);
  87. 	    }
  88. 	    sortkardebhai(n);
  89. 	   // cout<<endl;
  90. 	    for(ll i=0; i<n; i++)
  91. 	        pehlekaun[topso[i]]=i;
  92.         for(auto it=extra.begin(); it!=extra.end(); it++)
  93.         {
  94.             ll pehla=it->first, dusra=it->second;
  95.             if(pehlekaun[pehla]>pehlekaun[dusra])
  96.                 adj[dusra].push_back(pehla);
  97.             else
  98.                 adj[pehla].push_back(pehla);
  99.         }
  100.         for(ll i=0; i<n; i++)
  101.             for(ll j=0; j<adj[i].size(); j++)
  102.             {
  103.                 baaplog[adj[i][j]].insert(i);
  104.                 andar[adj[i][j]]++;
  105.             }
  106.         stack<ll> st;
  107.         for(auto x:topso)
  108.             st.push(x);
  109.         for(ll i=0; i<n; i++)
  110.             ghumakya[i]=false;
  111.         while(!st.empty())
  112.         {
  113.             ll u=st.top(), v;
  114.             st.pop();
  115.             ghumakya[u]=true;
  116.             if(!(andar[u]&1))
  117.                 continue;
  118.             if(baaplog[u].size()==0)
  119.             {
  120.                 flag=false;
  121.                 break;
  122.             }
  123.             auto it=baaplog[u].begin();
  124.             for( ; it!=baaplog[u].end(); it++)
  125.                 if(!ghumakya[*it])
  126.                 {
  127.                     v=*it;
  128.                     andar[u]--;
  129.                     andar[v]++;
  130.                     baaplog[u].erase(v);
  131.                     baaplog[v].insert(u);
  132.                     break;
  133.                 }
  134.             if(it==baaplog[u].end())
  135.             {
  136.                 flag=false;
  137.                 break;
  138.             }
  139.         }
  140.         unordered_set<ll> final[n];
  141.         for(ll i=0; i<n; i++)
  142.             for(auto it=baaplog[i].begin(); it!=baaplog[i].end(); it++)
  143.                 final[*it].insert(i);
  144.         if(flag)
  145.         {
  146.             for(ll i=0; i<m; i++)
  147.             {
  148.                 ll u=edges[i].first, v=edges[i].second;
  149.                 if(final[u].find(v)==final[u].end())
  150.                     cout<<"1 ";
  151.                 else
  152.                     cout<<"0 ";
  153.             }
  154.         }
  155.         else
  156.             cout<<"-1";
  157.         cout<<endl;
  158. 	}
  159. 	return 0;
  160. }
Success #stdin #stdout 0s 18464KB
comments (?)
stdin
copy 
2
4 4
1 2
1 3
2 4
3 4
3 3
1 2
2 3
1 3
stdout
copy 
1 1 0 0 
-1
https://ideone.com/PvaHdF
language:
C++14 (gcc 8.3)
created:
5 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!