做網(wǎng)站容易找工作嗎互聯(lián)網(wǎng)推廣有哪些方式
活動 - AcWing
給定一張圖,請你找出歐拉回路,即在圖中找一個環(huán)使得每條邊都在環(huán)上出現(xiàn)恰好一次。
輸入格式
第一行包含一個整數(shù)?t,t∈{1,2},如果?t=1,表示所給圖為無向圖,如果?t=2,表示所給圖為有向圖。
第二行包含兩個整數(shù)?n,m,表示圖的結(jié)點數(shù)和邊數(shù)。
接下來?m?行中,第?i?行兩個整數(shù)?vi,ui,表示第?i?條邊(從?11?開始編號)。
- 如果?t=1 則表示?vi 到?ui 有一條無向邊。
- 如果?t=2 則表示?vi 到?ui 有一條有向邊。
圖中可能有重邊也可能有自環(huán)。
點的編號從?1?到?n。
輸出格式
如果無法一筆畫出歐拉回路,則輸出一行:NO。
否則,輸出一行:YES,接下來一行輸出?任意一組?合法方案即可。
- 如果?t=1,輸出?m?個整數(shù)?p1,p2,…,pm。令?e=|pi|,那么?e?表示經(jīng)過的第?i?條邊的編號。如果?pi 為正數(shù)表示從?ve 走到?ue,否則表示從?ue 走到?ve。
- 如果?t=2,輸出?m?個整數(shù)?p1,p2,…,pm。其中?pi 表示經(jīng)過的第?i?條邊的編號。
數(shù)據(jù)范圍
1≤n≤105
0≤m≤2×105
輸入樣例1:
1
3 3
1 2
2 3
1 3
輸出樣例1:
YES
1 2 -3
輸入樣例2:
2
5 6
2 3
2 5
3 4
1 2
4 2
5 1
輸出樣例2:
YES
4 1 3 5 2 6
解析:?
一、在無向圖中(所有邊都是連通的):?
(1)存在歐拉路徑的充分必要條件:度數(shù)為奇數(shù)的點只能有0或2。?
(2)存在歐拉回路(起點和終點相同)的充分必要條件:度數(shù)為奇數(shù)的點只能有0個。?
二、在有向圖中(所有邊都是連通的):?
(1)存在歐拉路徑的充分必要條件:要么所有點的入度均等于入度;要么除了兩個點之外,其余所有的點的出度等于入度,剩余的兩個點:一個滿足出度比入度多1(起點),另一個滿足入度比出度多1(終點)。?
(2)存在歐拉回路(起點和終點相同)的充分必要條件:所有點的入度均等于出度。?
歐拉回路的dfs用邊來判重,不能用點。?
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>
#include<sstream>
#include<deque>
#include<unordered_map>
#include<unordered_set>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 1e5 + 5, M = 4e5 + 5, INF = 0x3f3f3f3f;int n, m;
int h[N], e[M], ne[M], idx;
int din[N], dout[N];
int ans[M], cnt;
bool used[M];
int type;void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}void dfs(int u) {//cout << "_______________________" << u << endl;for (int& i = h[u]; i != -1;) {if (used[i]) {i = ne[i];continue;}int t;if (type == 1) {t = i / 2 + 1;if (i & 1)t = -t;}else t = i + 1;used[i] = 1;if (type == 1) {used[i ^ 1] = 1;}int j = e[i];i = ne[i];dfs(j);ans[++cnt] = t;}
}int main() {cin >> type;cin >> n >> m;memset(h, -1, sizeof h);for (int i = 1,a,b; i <= m; i++) {scanf("%d%d", &a, &b);add(a, b);if (type == 1)add(b, a);din[b]++, dout[a]++;}if (type == 1) {for (int i = 1; i <= n; i++) {if (din[i] + dout[i] & 1) {cout << "NO" << endl;return 0;}}}else {for (int i = 1; i <= n; i++) {if (din[i] != dout[i]) {cout << "NO" << endl;return 0;}}}for (int i = 1; i <= n; i++) {if (h[i] != -1) {dfs(i);break;}}if (cnt < m) {cout << "NO" << endl;return 0;}cout << "YES" << endl;for (int i = cnt; i; i--) {printf("%d ", ans[i]);}return 0;
}