75分求助,最后两个点TLE
查看原帖
75分求助,最后两个点TLE
914688
zhangjinhuan楼主2023/11/18 21:40

QAQ

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <ctime>
#include <algorithm>
#include <typeinfo> 
#include <iomanip>
using namespace std;
const int N = 2e6 + 5;
int n,m,head[N],ntx[N],from[N],vtx[N],w[N],idx = 1;
void add(int a,int b,int c){
	ntx[idx] = head[a];
	head[a] = idx;
	from[idx] = a;
	vtx[idx] = b;
	w[idx] = c;
	idx++;
}
int num[N],low[N],dfn;
int cnt;
set<int> bcc[N];
stack<int> stk;
void dfs(int s,int fa){
	num[s] = low[s] = ++dfn;
	int r = 0;
	for(int i = head[s]; i; i = ntx[i]){
		if(!num[vtx[i]]){
			r++;
			stk.push(i);
			dfs(vtx[i],s);
			low[s] = min(low[s],low[vtx[i]]);
			if(low[vtx[i]] >= num[s]){
				cnt++;
				while(true){
					int k = stk.top();
					stk.pop();
					bcc[cnt].insert(from[k]);
					bcc[cnt].insert(vtx[k]);
					if(k == i){
						break;
					}
				}
			}
		}else if(num[vtx[i]] < low[s]&&vtx[i] != fa){
			stk.push(i);
			low[s] = min(low[s],num[vtx[i]]);
		}
	}
	if(!fa&&!r){
		bcc[++cnt].insert(s);
	}
}
set<int>::iterator it;
int main(){
	scanf("%d%d",&n,&m);
	for(int i = 1; i <= m; i++){
		int a,b;
		scanf("%d%d",&a,&b);
		if(a == b){
			continue;
		}
		add(a,b,1);
		add(b,a,1);
	}
	for(int i = 1; i <= n; i++){
		if(!num[i]){
			dfs(i,0);
		}
	}
	printf("%d\n",cnt);
	for(int i = 1; i <= cnt; i++){
		printf("%d ",bcc[i].size());
		for(it = bcc[i].begin(); it != bcc[i].end(); it++){
			printf("%d ",*it);
		}
		printf("\n");
	}
    return 0;
}
2023/11/18 21:40
加载中...