rt，目测为缩点板子

题目描述

一款游戏有n个行星，由m个传送门连接。当且仅当两个行星a和b之间存在一条从a到b和从b到a的路径时，它们属于同一个王国。你的任务是确定每个行星所属的王国。

输入格式

第一行输入两个整数n和m：行星和传送门的数量。行星编号为1,2,...,n。接下来的m行描述了传送门。每行有两个整数a和b：你可以通过传送门从行星a到行星b旅行。

输出格式

首先打印一个整数k：王国的数量。然后，为每个行星打印一个介于1和k之间的王国标签。可以打印任何有效的解决方案。

#include <bits/stdc++.h>
#define rep(i ,m ,n ,x) for (int i = (m) ;i <= (n) ;i += (x))
using namespace std ;
const int N = 2e5 + 7 ;
int n ,m ,dfn[N] ,low[N] ,head[N << 1] ,tot ,dcnt ,ccnt ,stk[N] ,stop ,scc[N] ;
bool instk[N] ;
struct edge {
	int to ,nxt ;
}e[N << 1] ;
namespace shin {
	template <typename T> inline void read (T &x) {
		x = 0 ;
		char ch = getchar () ;
		while (! isdigit (ch)) {
			ch = getchar () ;
		}
		while (isdigit (ch)) {
			x = (x << 1) + (x << 3) + (ch xor 48) ;
			ch= getchar () ;
		}
	}
	inline void add (int u ,int v) {
		e[++ tot].nxt = head[u] ;
		head[u] = tot ;
		e[tot].to = v ;
	}
	inline void tarjan (int cur) {
		dfn[cur] = low[cur] = ++ dcnt ;
		stk[++ stop] = cur ;
		instk[cur] = true ;
		for (int i = head[cur] ;i ;i = e[i].nxt) {
			int nex = e[i].to ;
			if (! dfn[nex]) {
				shin :: tarjan (nex) ;
				low[cur] = min (low[cur] ,low[nex]) ;
			}
			else if (instk[nex]) {
				low[cur] = min (low[cur] ,dfn[nex]) ;
			}
		}
		if (low[cur] == dfn[cur]) {
			ccnt ++ ;
			int now ;
			do {
				now = stk[stop --] ;
				instk[now] = false ;
				scc[now] = ccnt ;
			} while (now != cur) ;
		}
	}
}
int main () {
	shin :: read (n) ,shin :: read (m) ;
	rep (i ,1 ,m ,1) {
		int u ,v ;
		shin :: read (u) ,shin :: read (v) ;
		shin :: add (u ,v) ; 
	}
	rep (i ,1 ,n ,1) {
		if (! dfn[i]) shin :: tarjan (i) ;
	}
	cout << ccnt << '\n' ;
	rep (i ,1 ,n - 1 ,1) {
		cout << scc[i] << " " ; 
	}
	return cout << scc[n] << '\n' ,0 ;
}
//kafka & かみや