fork(2) download
copy 
  1. #include <iostream>
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. set<int> G[2005];
  5. int indegree[2005];
  6. bool vis[2005];
  7. int n;
  8. vector<int> top_sorted;
  9. set<int> taken;
  10. void dfs(int u)
  11. {
  12.     vis[u] = true;
  13.     auto i = G[u].end();
  14.     for(;i!=G[u].end();++i)
  15.     	if(!vis[*i])
  16.     		dfs(*i);
  17.     top_sorted.push_back(u);
  18. }
  19. int main()
  20. {
  21.  
  22.   cin>>n;
  23.   memset(vis,0,sizeof vis);
  24.   for(int i=1;i<=n;++i)
  25.   {
  26.     for(int j=1;j<=n;++j)
  27.     {
  28.         char c;
  29.         cin>>c;
  30.         if(c == '1')
  31.             G[i].insert(j);
  32.     }
  33.   }
  34.   for(int i=n;i>=1;--i)
  35.     if(!vis[i])
  36.         dfs(i);
  37.   vector<pair<int,int> > res;
  38.   for(int i=top_sorted.size()-1;i>=0;--i)
  39.   {
  40.     int u = top_sorted[i];
  41.     for(int j=1;j<=n;++j)
  42.         if(j!=u && (G[u].find(j) == G[u].end()) && (taken.find(j) == taken.end()))
  43.             res.push_back({u,j});
  44.  
  45.     taken.insert(u);
  46.   }
  47.   cout<<res.size()<<endl;
  48.   sort(res.begin(),res.end());
  49.   for(int i=0;i<res.size();++i)
  50.     cout<<res[i].first<<" "<<res[i].second<<endl;
  51.  
  52.  
  53.  
  54.  
  55.  
  56.  
  57. }
  58.  
Success #stdin #stdout 0s 3492KB
comments (?)
stdin
copy 
5
00000
10000
00000
01100
11010
stdout
copy 
10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
https://ideone.com/uzlXx3
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

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!