[AtCoder] [經典競程 90 題] 021 - Come Back in One Piece（★5）

題目連結: https://atcoder.jp/contests/typical90/tasks/typical90_u
題目大意:
給定一個 $N$ 個點 $M$ 條邊的有向圖，問有多少 $(x, y)$ 可以互相走到。

---

SCC 定義就是可以互相走到會在一起，所以建個 SCC 並數每個 CC 裡有多少點就好了。

#include <bits/stdc++.h>
using namespace std;

class SCC {
private:
  int n, num_;
  vector< vector< int > > G, rG;
  vector< int > ord, num;
  vector< bool > vis;
  void dfs( int u ) {
    if ( vis[ u ] ) return;
    vis[ u ] = 1;
    for ( int v : G[ u ] ) dfs( v );
    ord.push_back( u );
  }
  void rdfs( int u ) {
    if ( vis[ u ] ) return;
    num[ u ] = num_;
    vis[ u ] = 1;
    for ( int v : rG[ u ] ) rdfs(v);
  }
public:
  inline void init( int n_ ) {
    n = n_, num_ = 0;
    G.clear(); G.resize( n );
    rG.clear(); rG.resize( n );
    vis.clear(); vis.resize( n );
    num.resize( n );
  }
  inline void add_edge( int st, int ed ) {
    G[ st ].push_back( ed );
    rG[ ed ].push_back( st );
  }
  void solve() {
    fill( vis.begin(), vis.end(), 0 );
    for ( int i = 0 ; i < n ; ++ i )
      if ( not vis[ i ] ) dfs( i );
    reverse( ord.begin(), ord.end() );
    fill( vis.begin(), vis.end(), 0 );
    for ( int i : ord ) {
      if( not vis[ i ] ) {
        rdfs( i ); num_++;
      }
    }
  }
  inline int get_id( int x ) { return num[ x ]; }
  inline int count() { return num_; }
} scc;

int main() {
	ios_base::sync_with_stdio( false );
	cin.tie( nullptr );
	int n, m; cin >> n >> m;
	scc.init( n );
	for ( int i = 0 ; i < m ; ++ i ) {
		int u, v; cin >> u >> v;
		scc.add_edge( u - 1, v - 1 );
	}
	scc.solve();
	unordered_map< int, int64_t > cnt;
	for ( int i = 0 ; i < n ; ++ i ) {
		cnt[ scc.get_id( i ) ]++;
	}
	int64_t ans = 0;
	for ( auto [ _, v ] : cnt ) {
		ans += v * ( v - 1 ) / 2;
	}
	cout << ans << '\n';
	return 0;
}