제출 #394632

#제출 시각아이디문제언어결과실행 시간메모리
394632parsabahramiNetwork (BOI15_net)C++17
100 / 100
778 ms64700 KiB
#include <bits/stdc++.h>
 
using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
 
#define SZ(x)                       (int) x.size()
#define F                           first
#define S                           second

const int N = 5e5 + 10, MOD = 1e9 + 7;
int P[N], S[N], F[N], B[N], H[N], mn[N], M[N], n, m, timer = 0;
vector<pii> adj[N], L; pii E[N];

void preDFS(int v, int p = -1) {
	mn[v] = H[v]; M[v] = 1;
	for (pii u : adj[v]) {
		if (!M[u.F]) {
			H[u.F] = H[v] + 1; 
			preDFS(u.F, v);
			mn[v] = min(mn[v], mn[u.F]);
			if (mn[u.F] >= H[u.F]) B[u.S] = 1;
		} else if (u.F != p) mn[v] = min(mn[v], H[u.F]);
	}
}

int Find(int v) {
	return !P[v] ? v : P[v] = Find(P[v]);
}	

void Union(int u, int v) {
	u = Find(u), v = Find(v);
	if (u != v) P[u] = v;
	return; 
}

void DFS(int v, int p = -1) {
	S[v] = timer++;
	for (pii u : adj[v]) {
		if (u.F != p) DFS(u.F, v);
	}
}

int main() {
	scanf("%d", &n);
	if (n == 2) return !printf("-1\n");
    m = n - 1;
	for (int i = 1; i <= m; i++) {
		int u, v; scanf("%d%d", &u, &v);
		adj[u].push_back({v, i}); E[i] = {u, v};
		adj[v].push_back({u, i});
	}
	preDFS(1);
	for (int i = 1; i <= m; i++) {
		if (!B[i]) Union(E[i].F, E[i].S);
	}
	for (int i = 1; i <= n; i++) adj[i] = {};
	for (int i = 1; i <= m; i++) {
		if (B[i]) {
			int u = Find(E[i].F), v = Find(E[i].S);
			adj[u].push_back({v, i});
			adj[v].push_back({u, i});
		}
	}
	int rt = 1;
	for (int i = 1; i <= n; i++) if (i == Find(i) && SZ(adj[i]) > 1) rt = i;
	DFS(rt);
	for (int i = 1; i <= n; i++) {
		if (i != Find(i)) continue;
		if (SZ(adj[i]) == 1) L.push_back({S[i], i});
	}
	sort(L.begin(), L.end());
	if (!SZ(L)) return !printf("0\n");
	printf("%d\n", (SZ(L) + 1) / 2);
	for (int i = 0; i < (SZ(L) + 1) / 2; i++) {
		printf("%d %d\n", L[i].S, L[i + SZ(L) / 2].S);
	}
    return 0;
}
 

컴파일 시 표준 에러 (stderr) 메시지

net.cpp: In function 'int main()':
net.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   46 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
net.cpp:50:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   50 |   int u, v; scanf("%d%d", &u, &v);
      |             ~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...