放假前的最后一题

lxyt_415x @ 2023-08-24 10:25:20

by 1234567_scp @ 2023-08-24 12:01:51

#include<bits/stdc++.h>
using namespace std;
const int N=10010, M=100001;
int s[N], top;
bool flag[N];
int dfn[N],low[N],scc[N],team,num;
int head[N],nxt[M],to[M],t;
struct edge {
    int a, b;
    bool operator < (edge e) {
        return a<e.a || a==e.a && b<e.b;
    }
    bool operator == (edge e) {
        return a==e.a && b==e.b;
    }
    bool operator != (edge e) {
        return a!=e.a || b!=e.b;
    }
} e[M];
vector<int> g[N];
void tarjan(int x) {
    dfn[x]=low[x]=++num;
    flag[s[++top]=x]=true;
    for(int i=head[x];i;i=nxt[i]) {
        if(!dfn[to[i]]) {
            tarjan(to[i]);
            low[x]=min(low[x], low[to[i]]);
        }
        else if(flag[to[i]])
            low[x]=min(low[x], dfn[to[i]]);
    }
    if(dfn[x]==low[x]) {
        team++;
        int y;
        do {
            flag[y=s[top--]]=false;
            g[scc[y]=team].push_back(y);
        }while(x!=y);
    }
}
int main() {
    int n,m;
    scanf("%d%d", &n, &m);
    for(int i=1; i<=m; i++)
        scanf("%d%d", &e[i].a, &e[i].b);
    sort(e+1, e+m+1);
    int M=0;
    for(int i=1; i<=m; i++)
        if (e[i].a!=e[i].b && e[i]!=e[i-1])
            e[++M]=e[i];
    for(int i=1;i<=M;i++)
        nxt[++t]=head[e[i].a], to[head[e[i].a]=t]=e[i].b;
    for(int i=1;i<=n;i++)
        if(!scc[i])
            tarjan(i);
    printf("%d\n", team);
    memset(flag,0,sizeof(flag));
    for(int i=1; i<=team; i++)
        sort(g[i].begin(), g[i].end());
    sort(g+1, g+team+1, [&](vector<int> u, vector<int> v){return u[0]<v[0];});
    for(int i=1; i<=team; i++, puts(""))
        for(auto _: g[i])
            printf("%d ", _);
    return 0;
}

by 1234567_scp @ 2023-08-24 12:02:17

flag[to[i]]关键