[DFS]CF883G:Orientation of Edges

题目大意

给定一个N个点M条边且没有自环的图,图中既有有向边和无向边的图,从S出发,将所有的无向边改成有向边,求能够遍历到的最大最小点数,以及各自的任一方案。

题解

S开始刷一趟DFS,碰到有向边就DFS下去,无向边(u,v)则分两种,求最大时u\to v,求最小时v\to u(其中u是当前遍历到的点);易得这样是最优的;

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int N,M,S,Ans,TP[300005];
bool vis[300005],col[300005];
int tot,son[600005],nxt[600005],lnk[300005],Id[600005],tp[600005],Xs[600005];
inline void add(int x,int y,int id,int type,int A){son[++tot]=y;nxt[tot]=lnk[x];lnk[x]=tot;Id[tot]=id;tp[tot]=type;Xs[tot]=A;}
void DFS(int x,int l){
    Ans++;
    for (int i=lnk[x];i;i=nxt[i]){
        if (son[i]==l||vis[son[i]]) continue;
        if (tp[i]==2) col[Id[i]]=Xs[i];
        vis[son[i]]=1;DFS(son[i],x);
    }
}
void DFS_(int x,int l){
    Ans++;
    for (int i=lnk[x];i;i=nxt[i]){
        if (son[i]==l||vis[son[i]]) continue;
        if (tp[i]==2) col[Id[i]]=Xs[i]^1;
        else vis[son[i]]=1,DFS_(son[i],x);
    }
}
inline int read(){
    int Res=0;char ch=getchar();
    while (ch>'9'||ch<'0') ch=getchar();
    while (ch>='0'&&ch<='9') Res=Res*10+ch-'0',ch=getchar();
    return Res;
}
int main()
{
    N=read();M=read();S=read();
    for (int i=1;i<=M;i++){
        int t=read(),x=read(),y=read();
        add(x,y,i,t,1);
        if (t==2) add(y,x,i,t,0);
        TP[i]=t;
    }
    vis[S]=1;DFS(S,0);
    printf("%d\n",Ans);
    for (int i=1;i<=M;i++){
        if (TP[i]!=2) continue;
        if (col[i]) printf("+");else printf("-");
    }
    printf("\n");
    memset(vis,0,sizeof vis);Ans=0;
    memset(col,0,sizeof col);
    vis[S]=1;DFS_(S,0);
    printf("%d\n",Ans);
    for (int i=1;i<=M;i++){
        if (TP[i]!=2) continue;
        if (col[i]) printf("+");else printf("-");
    }
    return 0;
}
1 Comments
Leave a Reply