牛客练习赛25 E 定向图论：图论基础

链接：https://www.nowcoder.com/acm/contest/158/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。

【牛客练习赛25 E 定向】示例1
输入复制

3 3 1 2 1 3 2 3

输出复制

101

说明

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

备注:

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

思路：图论的简单应用吧。只要图中有桥就一定是impossible，否则就可以。先找到桥边，去掉桥边以后进行一遍dfs定向即可。
代码：

#include #define ll long long #define inf 0x3f3f3f3f #define N 1500005 #define M 1500005 using namespace std; namespace fastIO { #define BUF_SIZE 100000 //fread -> read bool IOerror = 0; inline char nc() { static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = buf + BUF_SIZE; if(p1 == pend) { p1 = buf; pend = buf + fread(buf, 1, BUF_SIZE, stdin); if(pend == p1) { IOerror = 1; return -1; } } return *p1++; } inline bool blank(char ch) { return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t'; } inline void read(int &x) { char ch; while(blank(ch = nc())); if(IOerror) return; for(x = ch - '0'; (ch = nc()) >= '0' && ch <= '9'; x = x * 10 + ch - '0'); } #undef BUF_SIZE }; using namespace fastIO; //void read(int &x){scanf("%d",&x); } int fg; int n,m; //n个点 m条边 struct node { int from,to,nex; int cut; //记录这条边是否为割边 }edge[2*M]; //双向边则 edge[i]与edge[i^1]是2条反向边 int head[N] ,edgenum; //在一开始就要 memset(head,-1,sizeof(head)); edgenum=0; int low[N],dfn[N],tarjin_time; void add(int u,int v) { node E={u,v,head[u],0}; edge[edgenum]=E; head[u]=edgenum++; } void tarjin(int u,int pre) { low[u]=dfn[u]= ++tarjin_time; int flag=1; //flag是阻止双向边的反向边 i和i^1 for(int i=head[u]; i!=-1; i=edge[i].nex) { int v=edge[i].to; if(flag&&v==pre) { flag=0; continue; } if(!dfn[v]) { tarjin(v,u); if(low[u]>low[v])low[u]=low[v]; if(low[v]>dfn[u])//是桥low[v]表示v能走到的最早祖先有重边且u是v的最早祖先则low[v]==dfn[u],所以不会当作桥 {fg=1; edge[i].cut=edge[i^1].cut=true; } } else if(low[u]>dfn[v])low[u]=dfn[v]; } } bool liantong; //是否连通 void find_edgecut() { memset(dfn,0,sizeof(dfn)); tarjin_time=0; tarjin(1,1); liantong=true; for(int i=1; i<=n; i++)if(!dfn[i]){liantong=false; return; } } bool vis[N]; void init(){ for(int i = 0; i<=n; i++)head[i] = -1; edgenum = 0; memset(vis, 0, sizeof(vis)); fg = 0; } void dfs(int u, int fa){ vis[u] = true; for(int i = head[u]; ~i; i = edge[i].nex){ int v = edge[i].to; if( edge[i].cut == 1)continue; if(edge[i^1].cut!=-1)edge[i].cut = -1; if(!vis[v]) dfs(v, u); } } int main(){ int u, v, Cas = 1; read(n); read(m); { init(); while(m--){ read(u); read(v); add(u, v); add(v, u); } find_edgecut(); for(int i = 1; i <= n; i++)if(!vis[i])dfs(i, i); if(fg){puts("impossible"); return 0; } for(int i = 0; i < edgenum; i+=2) if(edge[i].cut)printf("0"); else printf("1"); puts(""); } return 0; }