牛客练习赛25—E定向

题目链接：传送门
 

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
Special Judge, 64bit IO Format: %lld

题目描述

给一张无向图，你需要将边定向，使得定向后的有向图强连通。

输入描述:

第一行两个数n,m，表示点数和边数。
接下来m行，每个两个数x,y，表示x和y之间有条边。

输出描述:

如果不存在可行方案输出一行"impossible" ；
否则，输出一个长度为m的01串，描述你的方案，
第i个字符为1表示输入的第i条边定向为从x到y，为0表示从y到x。

示例1

输入

复制

3 3
1 2
1 3
2 3

输出

复制

101

说明

1->2->3->1，形成一个环 ，是强连通的。

备注:

1 ≤ n,m ≤ 106 ，保证无重边自环

解题思路：

dfs建立一颗树，所有树边从父亲指向儿子，返祖边从后代指向祖先。

假如这是一个联通图，且没有割边，那么祖先结点总能到达后代结点，而后代结点也能通过返祖边到达祖先结点。

所以只要图联通，且没有割边那么一定有解。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long llt;
const int INF = 0x3fffffff;
const int N = 1000010;
const int M = 100010;
const double pi = acos(-1);
const int mod = 1e9+7;
struct Edge{
int u,id,dir;
Edge*next;
}edge[N];
int Ecnt,cnt,val,low[N],dfn[N],e[N];
Edge*head[N];
void init()
{
Ecnt = cnt = val = 0;
fill(head,head+N,(Edge*)0);
}
void mkEdge(int a,int b,int id,int dir)
{
edge[Ecnt].u = b;
edge[Ecnt].id = id;
edge[Ecnt].dir = dir;
edge[Ecnt].next = head[a];
head[a] = edge+Ecnt++;
}
void dfs(int u,int fa)
{
low[u] = dfn[u] = ++cnt;
for(Edge*p = head[u]; p; p = p->next){
int v = p->u;
if(v == fa) continue;
//cout << u << " " << v << " " << p->dir << endl;
if(!dfn[v]){
dfs(v,u);
low[u] = min(low[u],low[v]);
if(low[v] > dfn[u]) val++;
e[p->id] = p->dir;
}else{
low[u] = min(low[u],dfn[v]);
if(dfn[v] < dfn[u])
e[p->id] = p->dir;
}
}
}
int main()
{
init();
int n,m,a,b;
scanf("%d%d",&n,&m);
for(int i = 0; i < m; ++i){
scanf("%d%d",&a,&b);
mkEdge(a,b,i,1);
mkEdge(b,a,i,0);
}
memset(low,0,sizeof(low));
memset(dfn,0,sizeof(dfn));
dfs(1,-1);
if(cnt != n || val != 0) printf("impossiblen");
else{
for(int i = 0; i < m; ++i){
printf("%d",e[i]);
}
printf("n");
}
return 0;
}

最后

以上就是激情大雁为你收集整理的牛客练习赛25—E定向的全部内容，希望文章能够帮你解决牛客练习赛25—E定向所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。