{テンプレート}Tarjan縮環-人工スタック
6702 ワード
ポイントセット+エッジセット+検索セット
#include
#include
#include
#include
using namespace std;
const int N=500500;
int m,n,S,q;
long long ans,Dist[N];
int Fir[N],Edge[2*N][2],tot_edge,head[N];
int Father[N];
int dfn[N],low[N],List[N];
bool vis[N];
int Data[N],bz[N];
int Stack[N][2];
int read(int &n)
{
char ch=' ';int q=0,w=1;
for(;(ch!='-')&&((ch<'0')||(ch>'9'));ch=getchar());
if(ch=='-')w=-1,ch=getchar();
for(;ch>='0' && ch<='9';ch=getchar())q=q*10+ch-48;n=q*w;return n;
}
void link(int x,int y)
{
if(!Fir[x]) head[x] = tot_edge + 1;
Edge[++ tot_edge][0] = Fir[x];
Fir[x] = tot_edge;
Edge[tot_edge][1] = y;
}
void tarjan(int x)
{
int I = 1;
bool P;
Stack[I][0] = x;
Stack[I][1] = 0;
while (I)
{
P = 1;
x = Stack[I][0];
if(!Stack[I][1])
{
bz[x] = vis[x] = 1,
List[ dfn[x] = low[x] = ++List[0] ]=x,
Stack[I][1] = Fir[x];
}
else
{
low[x] = min(low[x],low[Edge[Stack[I][1]][1]]),
Stack[I][1] = Edge[Stack[I][1]][0];
}
for(int i = Stack[I][1];i;i = Edge[i][0])
if(bz[Edge[i][1]])
{
low[x] = min(low[x],low[Edge[i][1]]);
}
else
if(!vis[Edge[i][1]])
{
Stack[I][1] = i;
Stack[++I][0] = Edge[i][1];
Stack[I][1] = 0;
P=0;
break;
}
if(P)
{
if(low[x] == dfn[x])
{
int t;
while( (t = List[ List[0]-- ]) != x )
{
bz[t] = 0;
Father[t] = x;
}
Father[x] = x;
bz[x] = 0;
}
I --;
}
}
}
int Getfather(int x)
{
return Father[x] = (Father[x]==x?x:Getfather(Father[x]));
}
int main()
{
int x,y;
read(n),read(m),read(q);
for(int i = 1;i <= m;i ++)
{
read(x),read(y);
link(x,y);
}
for(int i = 1;i <= n;i ++)
if(!vis[i])
tarjan(i);
for(int i = 1;i <= n;i ++)
if( (x=Getfather(i)) != i )
{
Edge[head[i]][0] = Fir[x];
Fir[x] = Fir[i];
Fir[i] = 0;
}
for(int i = 1;i <= n;i ++)
for(int j = Fir[i];j;j = Edge[j][0])
Edge[j][1]=Father[Edge[j][1]];
}