Submission #23239818

---

Source Code Expand

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
 
struct Edge {
  int to;
  long long w;
  Edge(int to, long long w) : to(to), w(w) {}
};
 
using Graph = vector<vector<int> >;
// using Graph = vector<vector<Edge> >;
 
template<class T> void chmax(T& a, T b) {
  if(a < b) a = b;
}
template<class T> void chmin(T& a, T b) {
  if(a > b) a = b;
}

 
struct UnionFind {
  vector<long long> par, siz;
 
  UnionFind(long long n) : par(n, -1), siz(n, 1){}
 
  long long root(long long x) {
    if(par[x] == -1) return x;
    else return par[x] = root(par[x]);
  }
 
  bool issame(long long x, long long y) {
    return root(x) == root(y);
  }
 
  bool unite(long long x, long long y) {
    x = root(x); y = root(y);
 
    if(x == y) return false;
 
    if(siz[x] < siz[y]) swap(x, y);
 
    par[y] = x;
    siz[x] += siz[y];
    return true;
  }
 
  long long size(long long x) {
    return siz[root(x)];
  }
};


int main() {
  int N, M;
  cin >> N >> M;
  vector<vector<bool> > move(N, vector<bool>(N, false));

  
  Graph G(N);

  rep(i, M) {
    int s, e;
    cin >> s >> e;
    G[s-1].push_back(e-1);
  }

  stack<int> p;

  rep(s, N) {
    p.push(s);
    while(!p.empty()) {
      int n = p.top();
      p.pop();

      // nから1stepで行けるところ
      for(auto next : G[n]) {
        if(move[s][next]) continue;
        p.push(next);
        move[s][next] = true;
      }  
    }
  }



  // N`2
  int ans = 0;
  rep(i, N) {
    rep(j, N) {
      if(i == j) {
        ans++;
        continue;
      }
      if(move[i][j]) ans++;
    }
  }

  cout << ans << endl;
}

Submission Info

Judge Result