[2017-2018 ACM-ICPC, NEERC, Southern Subregional Contest][Codeforces 883 G]Orientation of Edges

    题意：给出一个n个点m条边的图，边分有向边和无向边两种，要求从s出发，将所有无向边改成有向边，使从s能遍历到的点最多和最少的方案，输出遍历到的点数和方案。

    题解：从s出发DFS，求最多的方案就是把所有一端为当前点的无向边向外连，最少方案就把无向边向内连。

#include <bits/stdc++.h>
using namespace std;
const int maxn=3e5+10;

int head[maxn],nxt[maxn<<1],E[maxn<<1],T[maxn<<1],ID[maxn<<1],Dir[maxn<<1],Ecnt;
int ans[maxn],anscnt;
int n,m,s,cnt;

void Add_Edge(int x,int y,int t,int dir,int id) {nxt[++Ecnt]=head[x];head[x]=Ecnt;E[Ecnt]=y;T[Ecnt]=t;ID[Ecnt]=id;Dir[Ecnt]=dir;}

void Init()
{
	scanf("%d%d%d",&n,&m,&s);
	for (int i=0;i<m;i++)
	{
		int t,x,y;
		scanf("%d%d%d",&t,&x,&y);
		if (t==1) Add_Edge(x,y,0,0,0);
		else ++cnt,Add_Edge(x,y,1,0,cnt),Add_Edge(y,x,1,1,cnt);
	}
}

int vis[maxn];

void DFS1(int x)
{
	vis[x]=1;
	anscnt++;
	for (int i=head[x];i;i=nxt[i]) if (!vis[E[i]])
	{
		if (T[i]==0) DFS1(E[i]);
		else ans[ID[i]]=Dir[i],DFS1(E[i]);
	}
}

void Print()
{
	printf("%d\n",anscnt);
	for (int i=1;i<=cnt;i++) printf("%c",(ans[i]==0)?'+':'-');
	printf("\n");
}

void DFS2(int x)
{
	vis[x]=1;
	anscnt++;
	for (int i=head[x];i;i=nxt[i]) if (!vis[E[i]])
	{
		if (T[i]==0) DFS2(E[i]);
		else ans[ID[i]]=Dir[i]^1;
	}
}

int main()
{
	Init();
	DFS1(s);
	Print();
	memset(vis,0,sizeof(vis));
	memset(ans,0,sizeof(ans));
	anscnt=0;
	DFS2(s);
	Print();
	return 0;
}