[TIOJ] 1481. [Interactive] 航線規劃問題
題目連結:http://tioj.infor.org/problems/1481
一個小觀察,$\forall x \in \mathbb{N},gcd(x, x+1)=1$,所以這題每個邊的編號其實就是DFS時每個邊被遍歷到了順序。
一個小觀察,$\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);
}
}
留言
張貼留言