fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <set>
  4.  
  5. using namespace std;
  6.  
  7. struct vertex{			
  8.     int used,colour;
  9.     vector<int>graph,graph_transposed;
  10. };
  11.  
  12. void dfs_g(int v, vector<vertex>&components, vector<int>&list){
  13.     components[v].used = 1;
  14.     for (int i = 0; i < components[v].graph.size(); i++){
  15.         if(components[components[v].graph[i]].used!=1) dfs_g(components[v].graph[i],components,list);
  16.     }
  17.     list.push_back(v);
  18. }
  19.  
  20. void dfs_tg(int v, int color, vector<vertex>&components){
  21.     components[v].used=2;
  22.     components[v].colour=color;
  23.     for (int i=0; i<components[v].graph_transposed.size(); i++){
  24.         if (components[components[v].graph_transposed[i]].used != 2)dfs_tg(components[v].graph_transposed[i],color,components);
  25.     }
  26. }
  27.  
  28. int main(){
  29. 	int n,m,color=0,answer=0;
  30.     cin>>n>>m;
  31. 	vector<int>list(n);
  32. 	vector<vertex>components(n);
  33. 	set<int>ribs[10000];
  34.     for(int i=0; i<m; i++){
  35.         int a,b;
  36.         cin>>a>>b;
  37.         components[a-1].graph.push_back(b-1);
  38.         components[b-1].graph_transposed.push_back(a-1);
  39.     }
  40.  
  41.     for (int i=0; i<n; i++){
  42.         if (components[i].used!=1)dfs_g(i,components,list);
  43.     }
  44.     for (int i=list.size()-1; i>=0; i--){
  45.         if (components[list[i]].used != 2){
  46.         	dfs_tg(list[i], color, components);
  47.         	color++;
  48.         }
  49.     }
  50.     for(int i=0; i<n; i++){
  51.         for(int j=0; j<components[i].graph.size(); j++){
  52.             if(components[i].colour!=components[components[i].graph[j]].colour){
  53.                 ribs[components[i].colour].insert(components[components[i].graph[j]].colour);
  54.             }
  55.         }
  56.     }
  57.     for(int i=0; i<10000; i++)answer+=ribs[i].size();
  58.     cout<<answer;
  59.     return 0;
  60. }
Success #stdin #stdout 0s 15584KB
comments (?)
stdin
copy 
6 9
1 2
2 4
4 1
4 2
3 2
2 6
3 5
5 3
6 2
stdout
copy 
1
https://ideone.com/gW78jM
language:
C++ (gcc 8.3)
created:
7 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!