[TIOJ] 1481. [Interactive] 航線規劃問題

題目連結:http://tioj.infor.org/problems/1481

---

一個小觀察，$\forall x \in \mathbb{N},gcd(x, x+1)=1$，所以這題每個邊的編號其實就是DFS時每個邊被遍歷到了順序。

#include <bits/stdc++.h>
#include "lib1481.h"
using namespace std;
typedef pair<int,int> PII;
#define FF first
#define SS second
#define PB push_back
const int V = 2000+5, E = 20000+5;

bitset<E> visited;
vector<PII> G[V];
int ans[E], cnt=0;

void dfs(int);

int main(){
	Init();
	int n, m; scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++){
		int u, v; scanf("%d%d",&u,&v);
		G[u].PB({v, i});
		G[v].PB({u, i});
	}
	dfs(1);
	Possible();
	for(int i=0;i<m;i++) Number(ans[i]);
	Finish();
	return 0;
} 

void dfs(int w){
	for(auto i: G[w]){
		int v = i.FF, id = i.SS;
		if(visited[id]) continue;
		visited[id]=1;
		ans[id]=++cnt;
		dfs(v);
	}
}