tarjan

const int  maxn = 4e5 + 5
#define INF 1000000000
#define MOD 1000000007
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
vector<int> G[maxn];
int n,dfn[maxn],low[maxn],st[maxn];
int vis[maxn];
int cmp[maxn],cnt,tot,t;
void (int v){
    dfn[v] = low[v] = ++tot;
    vis[v] = 1;
    st[t++] = v;
    for(auto to:G[v]){
        if(!vis[to]){
            dfs(to);
            low[v] = min(low[v],low[to]);
        }
        else if(vis[to]==1) low[v]=min(low[v],dfn[to]);
    }
    if(dfn[v] == low[v]){
        int u;
        cnt++;
        do{
            u = st[--t];
            cmp[u] = cnt;
            vis[u] = 2;
        }while(u != v);
        
    }
}
int tarjan(){
    t = tot = cnt = 0;
    memset(vis,0,sizeof(vis));
    for(int i = 1;i <= n;i++) if(!dfn[i]) dfs(i);
    return cnt;
}
int main(){
    return 0;
}

const int maxn = 4e5 + 5;
typedef long long ll; 
int cnt, color[maxn]; 
int tot, dfn[maxn], low[maxn], st[maxn], top, vis[maxn];
std::vector<int> G[maxn];
std::vector<char> g[maxn];//缩点后的图
void clear(int n) {
    tot = top = cnt = 0;
    for (int i = 1; i <= n; i++) {
        dfn[i] = vis[i] = color[i] = 0;
    }
}
void (int u) {
    dfn[u] = low[u] = ++tot;
    st[++top] = u; vis[u] = 1;
    int k = 0;
    for (int& v: G[u]) {
       if (v == f && !k) {
           k++; continue;
        } 
        if (!vis[v]) {
            dfs(v); 
            low[u] = min(low[u], low[v]);
        } 
        else if (vis[v]) low[u] = min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u]) {
      cnt++; int t = 0;
       do {
            t = st[top--];
            color[t] = cnt;
            vis[t] = 0;
        } while (t != u);
    }
}
void tarjan(int n) {
    clear();
 for (int i = 1; i <= n; i++) if (!dfn[i]) dfs(i, 0);
   for (int i = 1; i <= n; i++) g[i].clear();
    for (int i = 1; i <= n; i++) {
        int u = color[i];
        for (int& x: G[i]) {
          int v = color[x];
            if (u != v) {
              g[u].push_back(v);
            }
        }
     }
}