tarjan TLE on #72求调
查看原帖
tarjan TLE on #72求调
991489
_Memory楼主2024/8/9 11:39
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
const int M = 3e5 + 5;
int head[N], low[N], dfn[N],scc[N], root;
bool vis[N], ins[N];
int n, m, sec;
int cnt, num, ans;
bool flag = false;
stack<int> s;
struct node{
	int v, w, next;
}edge[M * 2];

int qwq[N][2];
struct nodeb{
	int v, u;
}bri[M * 2];
int bri_cnt ;
void addb(int u, int v){
	bri[bri_cnt].u = min(u, v);
	bri[bri_cnt].v = max(u, v);
	bri_cnt++;
}
bool cmp(nodeb x, nodeb y){
	if(x.u != y.u) return x.u < y.u;
	return x.v < y.v;
}
void add(int u, int v){
	edge[cnt].v = v;
	edge[cnt].next = head[u];
	head[u] = cnt;
	cnt++;
}
void init(){
	memset(head, -1, sizeof(head));
	memset(low, 0, sizeof(low));
	memset(dfn, 0, sizeof(dfn));
	memset(vis, false, sizeof(vis));
	cnt = num = 0;
}
void tarjan(int u, int fa){
	int count = 0;
	low[u] = dfn[u] = ++num;
	vis[u] = true;
	s.push(u);
	for(int i = head[u]; ~i; i = edge[i].next){
		int v = edge[i].v;
		if(v == fa) continue;
		if(!dfn[v]){
			tarjan(v, u);
			low[u] = min(low[u], low[v]);
		    qwq[++ans][0] = u, qwq[ans][1] = v;
			if(dfn[u] < low[v]){
				cout << 0;
				exit(0);
			}
		}
		else {
			low[u] = min(low[u], dfn[v]);
			if(dfn[u] > dfn[v]){
				qwq[++ans][0] = u, qwq[ans][1] = v;
			}
			
		}
    }
}
int main(){
	scanf("%d%d", &n, &m);
	init();
	for(int i = 1; i <= m; i++){
		int u, v;
		scanf("%d%d", &u, &v);
		add(u, v);
		add(v, u);
	}
	for(int i = 1; i <= n; i++){
		if(!dfn[i]){
			root = i;
			tarjan(i, i);
		}
	}
    for(int i = 1; i <= ans; i++){
    	printf("%d %d\n" ,qwq[i][0], qwq[i][1]);
    }
//	cout << sec << endl;

	return 0;
}
2024/8/9 11:39
加载中...