0pts

P8436 【模板】边双连通分量

LuoFeng_Nanami @ 2023-10-18 20:05:21


#include<bits/stdc++.h>
#define ll long long
#define rll register ll
#define F(i,a,b) for(rll i=a;i<=b;i++)
#define Fdn(i,a,b) for(rll i=a;i>=b;i--)
#define int ll
#define itn int
#define Sort sort(a + 1,a + n + 1)
#define SortCmp sort(a + 1,a + n + 1,cmp)
#define R(n) n = read()
#define Bk break
#define Pc putchar

using namespace std;
namespace IO{
    char ibuf[(1<<20)+1],*iS,*iT;
    #if ONLINE_JUDGE
    #define gh() (iS==iT?iT=(iS=ibuf)+fread(ibuf,1,(1<<20)+1,stdin),(iS==iT?EOF:*iS++):*iS++)
    #else
    #define gh() getchar()
    #endif
    #define reg register
    inline ll read(){
        reg char ch=gh();
        reg ll x=0;
        reg char t=0;
        while(ch<'0'||ch>'9')   t|=ch=='-',ch=gh();
        while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=gh();
        return t?-x:x;
    }
    inline void writ(ll x)
    {
        if(x < 0){
            putchar('-');
            x = -x;
        }
        if(x > 9) 
            writ(x / 10);
        putchar(x % 10 + '0');
    }
    inline void write(ll x,char c)
    {
        writ(x);
        putchar(c);
    }
}
using IO::read;
using IO::writ;
using IO::write;
#define umap unordered_map
#define uset unordered_set
#define ld long double
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
const ll ll_INF=9223372036854775807;
const int INF = 0x7fffffff;
namespace mySTL{
    inline ll max(ll a,ll b){return a>b?a:b;}
    inline ll min(ll a,ll b){return a<b?a:b;}
    inline ld min(ld a,ld b){return a<b?a:b;}
    inline ld max(ld a,ld b){return a>b?a:b;}
    inline void swap(ll &a,ll &b){a^=b,b^=a,a^=b;}
    inline ll pw(ll a,ll b,ll p){if(b==0)return 1;
    if(b==1)return a%p;
    ll mid=pw(a,b/2,p)%p;
    if(b&1)return mid*mid%p*a%p;else{return mid*mid%p;}}
    inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
    inline ll lcm(ll a,ll b){return a*b/gcd(a,b);}
}
using namespace mySTL;

const int inf = 0x3f3f3f3f,mod = 1e9 + 7; 
const int maxn = 5e5 + 7, maxm = 2e6 + 7;

struct edge{
    int to, nxt;
}G[maxm];

int head[maxn];
int n, m;
int tot = 1;
bool bridge[maxn];
int __dfn;
int dfn[maxn], low[maxn];
bool c[maxn];
int dcc;

vector<int> ans[maxn];

inline void add(int u, int v){ G[++tot].to = v, G[tot].nxt = head[u], head[u] = tot; }

inline void Tarjan(int fa, int u){
    low[u] = dfn[u] = ++__dfn;
    for(int i = head[u]; i; i = G[i].nxt){
        int v = G[i].to;
        if(!dfn[v]){
            Tarjan(i, v);
            low[u] = min(low[v], low[u]);
            if(low[v] > dfn[u])
                bridge[i] = bridge[i ^ 1] = 1;
        } else if(i != (fa ^ 1))
            low[u] = min(low[u], dfn[v]);
    }
}

inline void dfs(int u, int yousa){
    c[u] = 1;
    ans[yousa].pb(u);
    for(int i = head[u]; i; i = G[i].nxt){
        int v = G[i].to;
        if(c[v] || bridge[i])
            continue;
        dfs(v, yousa);
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    R(n), R(m);
    F(i, 1, m){
        int u = read(), v = read();
        if(u != v)
            add(u, v), add(v, u);
    }
    F(i, 1, n)
        if(!dfn[i])
            Tarjan(0, i);
    F(i, 1, n)
        if(!c[i])
            dfs(i, ++dcc);  
    write(dcc, '\n');

    F(i, 1, dcc){
        write(ans[i].size(), ' ');
        for(auto j : ans[i])
            write(ans[i][j], ' ');
        cout << endl;
    }

    return 0;
}

|