CF118E WAon84
查看原帖
CF118E WAon84
326254
LonginusMonkey楼主2023/11/17 11:37

wrong answer on #84

how I can solve it

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 300100;
struct node{
	int to, idx;
};
vector<node> vec[maxn];
int vis[maxn];
bool bl;
int depth[maxn];
int arr[maxn],fa[maxn];
void dfs(int index, int back) {
	fa[index] = back;
	depth[index] = depth[back] + 1;
	vis[index] = 1;
	for(int i=0; i<vec[index].size(); ++i) {
		if(vec[index][i].to == back) continue;
		if(vis[vec[index][i].to]) {
			arr[fa[vec[index][i].to]]--, arr[index]++; continue;
		}
		dfs(vec[index][i].to, index);
	}
}
void dfs2(int index, int back) {
	for(int i=0; i<vec[index].size(); ++i) {
		if(depth[vec[index][i].to] != depth[index] + 1) {
			continue;
		}
		dfs2(vec[index][i].to, index);
		arr[index] += arr[vec[index][i].to];
	}
	if(arr[index] <= 0) {
		bl = 1;
	}
}
int ans[maxn];
void dfs3(int index=1, int back=0) {
	for(int i=0; i<vec[index].size(); ++i) {
		if(vec[index][i].to == back) {
			continue;
		}
		if(depth[vec[index][i].to] == depth[index] + 1) cout << index << " " <<vec[index][i].to<<endl;
		else if(depth[vec[index][i].to] < depth[index])cout << index << " " << vec[index][i].to <<endl;
		if(depth[vec[index][i].to] == depth[index] + 1) dfs3(vec[index][i].to, index);
	}
}
struct node2{
	int u, v;
}edge[maxn];
signed main() {
	int n, m; cin >> n >> m;
	for(int i=1; i<=m; ++i) {
		int u, v; cin >> u >> v; edge[i].u = u; edge[i].v = v;
		vec[u].push_back({v, i}); vec[v].push_back({u, i});
	}
	dfs(1, 0);
	dfs2(1, 0);
	if(bl) {
		cout << 0;
	} else {
		dfs3();
	}
	return 0;
}
2023/11/17 11:37
加载中...