[TIOJ 1481] 航線規劃問題

作法：

這題蠻有梗的XD，一個重要的觀察是 x 和 x+1 互質，所以只要隨便一個點對他DFS，經過的邊依序標上 1 , 2 , ... , m 就可以了。因為如果這個點是DFS樹上的非葉節點，那他顯然滿足條件，否則如果它本身就是葉節點那就不需要有限制條件了，所以他至少有一條回邊，而這條回邊標上的值就等於祖先到他的邊的值加一，所以也會滿足條件了。

code :

#include<bits/stdc++.h>
#include"lib1481.h"
using namespace std;
const int maxn=5000+10 , maxm=1000000+10 ;
 
struct P{int from,to;};
 
bool vis[maxn] ;
int ans[maxm],cnt=0 ;
vector<int> v[maxn] ;
vector<P> edge ;
 
void dfs(int x)
{
    for(auto i : v[x]) if(!vis[i])
    {
        int to= edge[i].from==x ? edge[i].to : edge[i].from ;
        vis[i]=1 ; ans[i]=++cnt ;
        dfs(to) ;
    }
}
 
main()
{
    Init() ;
    int n,k ; scanf("%d%d",&n,&k) ;
    for(int i=0;i<k;i++)
    {
        int x,y ; scanf("%d%d",&x,&y) ;
        edge.push_back((P){x,y}) ;
        v[x].push_back(i) ;
        v[y].push_back(i) ;
    }
    Possible() ;
    dfs(1) ;
    for(int i=0;i<k;i++) Number(ans[i]) ;
    Finish() ;
}