codeforces 1391E Pairs of Pairs dfs树的性质

https://codeforces.com/problemset/problem/1391/E

题意：给一个无向图，找出以下任意一种输出答案

1，长度>=n/2(上界）的简单路径（没有同一个点走2次的路径）

2，点对树>=n/2（上界）的点对集，使得点对集内部的任意两个点对的4个点，边数不超过2

解法：

根据dfs树的性质，每个点x的出边只有树边和返祖边两种，返祖边只会连到x的祖先节点，所以任意一个节点的两颗子树没有横向边。

这个题先从某个点导出一颗dfs树，如果深度>=n/2（上界），直接输出路径即可。

否则，直接让同深度的点配对即可，深度低于n/2（上界），树必然宽，横向同深度的点对配对后加起来总点对树一定>=n/2（上界）。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=500100;

const int INF=(1<<29);

int n,m;

int u,v;

vector<int> G[maxn];

vector<int> T[maxn];

vector<int> node[maxn];

int dep[maxn];

int max_dep[maxn];

vector<int> path;

vector<pair<int,int> > prs;

bool vis[maxn];

void init(){

    for(int i=0;i<=n;i++) G[i].clear(),node[i].clear(),dep[i]=0,vis[i]=0,max_dep[i]=0,T[i].clear();

    path.clear();prs.clear();

}

void input(){

    for(int i=1;i<=m;i++){

        scanf("%d%d",&u,&v);

        G[u].push_back(v);

        G[v].push_back(u);

    }

}

void dfs(int u,int f){

    if(vis[u]) return;

    vis[u]=1;

    if(u!=1) T[f].push_back(u);

    for(int i=0;i<G[u].size();i++){

        int v=G[u][i];

        if(v==f) continue;

        dfs(v,u);

    }

}

void go(int u){

    path.push_back(u);

    int next=u;

    for(int i=0;i<T[u].size();i++){

        int v=T[u][i];

        if(max_dep[v]>=max_dep[next]) next=v;

    }

    if(next==u) return;

    go(next);

}

void get_d(int u,int f,int d){

    dep[u]=d;

    max_dep[u]=d;

    node[d].push_back(u);

    for(int i=0;i<T[u].size();i++){

        int v=T[u][i];

        get_d(v,u,d+1);

        max_dep[u]=max(max_dep[u],max_dep[v]);

    }

}

void solve(){

    init();

    input();

    dfs(1,0);

    get_d(1,0,1);

    if(max_dep[1]>=(n+1)/2){

        go(1);

        puts("PATH");

        cout<<(int)path.size()<<endl;

        for(int i=0;i<path.size();i++) cout<<path[i]<<" ";cout<<endl;

    }

    else{

        for(int i=2;i<=max_dep[1];i++){

            if((int)node[i].size()<2) continue;

            for(int j=1;j<node[i].size();j+=2) prs.push_back(make_pair(node[i][j-1],node[i][j]));

        }

        puts("PAIRING");

        cout<<(int)prs.size()<<endl;

        for(int i=0;i<prs.size();i++) cout<<prs[i].first<<" "<<prs[i].second<<endl;

    }

}

int main(){

    // freopen("in.txt","r",stdin);

    int T;cin>>T;

    while(~scanf("%d%d",&n,&m)) solve();

    return 0;

}

另一点就是把长程序分解分模块写，可以减少bug，更好排查，出错的时候更容易理清主体思路，思路永远优先于码速。

巴特西

codeforces 1391E Pairs of Pairs dfs树的性质

最新文章

热门文章