[AtCoder] [經典競程 90 題] 021 - Come Back in One Piece(★5)
題目連結: https://atcoder.jp/contests/typical90/tasks/typical90_u
題目大意:
給定一個 $N$ 個點 $M$ 條邊的有向圖,問有多少 $(x, y)$ 可以互相走到。
SCC 定義就是可以互相走到會在一起,所以建個 SCC 並數每個 CC 裡有多少點就好了。
題目大意:
給定一個 $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;
}
留言
張貼留言