稳定性(单向图tarjen)

Problem2 稳定性(cp.cpp/c/pas)

【题目描述】

有2*n个装置,其中奇数编号的为供电装置,偶数编号的为用电装置。

第i2-1个装置通过单向导线第i2个装置输送能量(它们称为第i对装置)。除此之外还有m条单向导线。

第i对装置是稳定的,当且仅当:直接连接2者的单向导线损坏时,仍然有一个供电方案使得每个供电装置给一个用电装置供电,且每个用电装置只由一个供电装置供电。

求每对装置稳定与否。

【输入格式】

第一行2个整数n,m。

接下来m行,每行2个整数a、b,表示a往b有一条单向导线。保证a为奇数,b为偶数。

【输出格式】

输出n行,若第i对装置是稳定的,输出“~”,否则输出“@”

 

【样例输入】

2 1

3 2

【样例输出】

@

@

【样例输入2】

2 2

3 2

1 4

【样例输出2】

~

~

【数据范围】

对于20%:N<=10

对于40%:N<=100

对于60%:N<=1000

对于100%:N<=100000,M<=2*N

注意Tarjen模板。

Ps:边最多有300000(原来的n条边+另外m条单向边)

#include<cstdio>

include<algorithm>

include<functional>

include<iostream>

include<cstdlib>

include<cstring>

include<cmath>

using namespace std;

define MAXN (200000+10)

define MAXM (300000+10)

int edge[MAXM],pre[MAXM],next[MAXM],size=0; void addedge(int u,int v) { edge[++size]=v; next[size]=pre[u]; pre[u]=size; } int t[MAXN],tim=0,dfs[MAXN]; int s[MAXN],tot=0,n,m; int kind=0,h[MAXN]; bool b[MAXN],numk[MAXN]; void tar(int u) { t[u]=dfs[u]=++tim;b[u]=1; s[++tot]=u; for (int p=pre[u];p;p=next[p]) { int &v=edge[p]; if (!b[v]) tar(v),dfs[u]=min(dfs[u],dfs[v]); else if (!h[v]) dfs[u]=min(dfs[u],t[v]); } if (dfs[u]==t[u]) { kind++; bool flag=0; while (s[tot]!=u) h[s[tot--]]=kind,flag=1; h[s[tot--]]=kind; numk[kind]=flag; } } int main() { freopen("cp.in","r",stdin); freopen("cp.out","w",stdout); scanf("%d%d",&n,&m); memset(pre,0,sizeof(pre)); memset(b,0,sizeof(b)); memset(h,0,sizeof(h)); for (int i=1;i<=n;i++) addedge(2i-1,2i); for (int i=1;i<=m;i++) { int u,v; scanf("%d%d",&u,&v); addedge(v,u); } for (int i=2;i<=2*n;i+=2) { if (!b[i]) tar(i); if (numk[h[i]]) printf("~\n"); else printf("@\n"); }

return 0;

}