Facebook
From Sexy Anoa, 7 Years ago, written in C++.
Embed
Download Paste or View Raw
Hits: 287
  1. #include <iostream>
  2. #include <vector>
  3. #include <stack>
  4. using namespace std;
  5.  
  6. vector <int> *Graf;
  7. vector <int> *Trans;
  8. stack <int> topSort;
  9. int *count;
  10.  
  11. struct vert{
  12.       int number;
  13.       bool f_visit;
  14.       bool s_visit;
  15. };
  16.  
  17. vert *Vert;
  18.  
  19. void dfs(int start){
  20.       Vert[start].f_visit = 1;
  21.       for(int i = 0; i < (int)Graf[start].size(); i++){
  22.               if(Vert[Graf[start][i]].f_visit == 0){
  23.                       dfs(Graf[start][i]);
  24.               }
  25.       }
  26.       topSort.push(start);
  27. }
  28.  
  29. void allDFS(int n){
  30.       for(int i = 1 ; i <= n; i++){
  31.               count[i] = 0;
  32.               if(!Vert[i].f_visit){
  33.                       dfs(i);
  34.               }
  35.       }
  36. }
  37.  
  38. void sss(int start, int number){
  39.       Vert[start].s_visit = true;
  40.       Vert[start].number = number;
  41.       count[number]++;
  42.  
  43.       for(int i = 0; i < (int)Trans[start].size(); i++){
  44.               if(Vert[Trans[start][i]].s_visit == false){
  45.                       sss(Trans[start][i], number);
  46.               }
  47.       }
  48. }
  49.  
  50. void allSSS(int n){
  51.       int number = 1;
  52.       while(!topSort.empty()){
  53.               if(Vert[topSort.top()].s_visit == false){
  54.                       sss(topSort.top(), number++);
  55.               }
  56.               topSort.pop();
  57.       }
  58. }
  59.  
  60. void readDATA(int n, int m){
  61.       for(int i = 1; i <= m; i++){
  62.               int a, b, c;
  63.               cin >> a >> b >> c;
  64.  
  65.               if(c == 0){
  66.                       Graf[b].push_back(a);
  67.                       Graf[a + n].push_back(b + n);
  68.  
  69.                       Trans[a].push_back(b);
  70.                       Trans[b + n].push_back(a + n);
  71.               }else{
  72.                       Graf[b].push_back(a + n);
  73.                       Graf[a + n].push_back(b);
  74.  
  75.                       Trans[b].push_back(a + n);
  76.                       Trans[a + n].push_back(b);
  77.               }
  78.       }
  79. }
  80.  
  81. void declareSTRUCTURE(int n){
  82.       Vert = new vert[2 * n + 1];
  83.       Graf = new vector<int>[2 * n + 1];
  84.       Trans = new vector<int>[2 * n + 1];
  85.       count = new int[2 * n + 1];
  86.  
  87.       for(int i = 1; i <= 2 * n; i++){
  88.               Vert[i].number = 0;
  89.               Vert[i].f_visit = false;
  90.               Vert[i].s_visit = false;
  91.       }
  92. }
  93.  
  94. void deleteSTRUCTURE(int n){
  95.       delete [] Vert;
  96.       delete [] Graf;
  97.       delete [] Trans;
  98.       delete [] count;
  99. }
  100.  
  101. void printRESULT(int n){
  102.       for(int i = 1; i <= n / 2; i++){
  103.               if(Vert[i].number == Vert[i + n / 2].number)
  104.                       count[Vert[i].number]--;
  105.       }
  106.       for(int i = 1; i <= n / 2; i++)
  107.               cout << max(count[Vert[i].number] - 1, 0) << " ";
  108.       cout << endl;
  109. }
  110.  
  111. int main(){
  112.       ios_base::sync_with_stdio(false);
  113.       int z;
  114.       cin >> z;
  115.  
  116.       while(z--){
  117.               int n, m;
  118.               cin >> n >> m;
  119.  
  120.               declareSTRUCTURE(n);
  121.               readDATA(n, m);
  122.               allDFS(2 * n);
  123.               allSSS(2 * n);
  124.               printRESULT(2 * n);
  125.               deleteSTRUCTURE(n);
  126.       }
  127.       return 0;
  128. }