WA求调,悬赏关注
查看原帖
WA求调,悬赏关注
999274
CNS_5t0_0r2楼主2024/7/4 16:06
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 9,M = 2e6 + 9;
struct edge{
    int to,nex;
} e[M << 1];
int ecnt = 1,head[N];
void addedge(int u,int v){
    ecnt++;
    e[ecnt] = (edge){v,head[u]};
    head[u] = ecnt;
}
int n,m,x,y;
int id,cnt,dfn[N],low[N];//id表示DFS序
int ans;
vector<int> v_dcc[N];//ans[i]:第i个连通分量的所有点
stack<int> s;
void dfs(int cur,int last){//cur表示当前顶点,last表示上一条边的编号
	int child = 0;
    id++;
    dfn[cur] = id;
    low[cur] = id;//当前顶点一定能到自己。
    s.push(cur);
    for(int i = head[cur];i;i = e[i].nex){
        if(i != (last ^ 1)){//不是上一条边的反向边
            int v = e[i].to,Top;
            if(!dfn[v]){
            	child++;
                dfs(v,i);
                low[cur] = min(low[cur],low[v]);
                if(low[v] >= dfn[cur]){
        			cnt++;
        			v_dcc[cnt].push_back(cur);
        			do{
        		    	Top = s.top();s.pop();
            			v_dcc[cnt].push_back(Top);
        			}while(Top != v);
				}
            }
            else//肯定不是父节点 
                low[cur] = min(low[cur],dfn[v]);
        }
    }
}


bool cmp(vector<int> x,vector<int> y){
	int len = min(x.size(),y.size());
	for(int i = 0;i < len;i++){
		if(x[i] < y[i])
			return true;
		else if(x[i] > y[i])
			return false;
	}
	return x.size() < y.size();
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i = 1;i <= m;i++){
        cin >> x >> y;
        if(x == y)
            continue;
        addedge(x,y);
        addedge(y,x);
    }

    for(int i = 1;i <= n;i++)
        if(!dfn[i])
            dfs(i,0);

	cout << cnt << '\n';
	sort(v_dcc + 1,v_dcc + cnt + 1,cmp);
	for(int i = 1;i <= cnt;i++){
    	int siz = v_dcc[i].size();
    	sort(v_dcc[i].begin(),v_dcc[i].end());
    	for(int j = 0;j < siz;j++)
    		cout << v_dcc[i][j] << ' ';
    	cout << '\n';
	}
    return 0;
}
2024/7/4 16:06
加载中...