POJ 2553(The Bottom of a Graph-缩点求出度)

Language:
The Bottom of a Graph
Time Limit: 3000MS   Memory Limit: 65536K
Total Submissions: 7308   Accepted: 3003

Description

We will use the following (standard) definitions from graph theory. Let V be a nonempty and finite set, its elements being called vertices (or nodes). Let E be a subset of the Cartesian product V×V, its elements being called edges.
Then G=(V,E) is called a directed graph. 
Let n be a positive integer, and let p=(e1,...,en) be a sequence of length n of edges ei∈E such that ei=(vi,vi+1) for a sequence of vertices (v1,...,vn+1).
Then p is called a path from vertex v1 to vertex vn+1 in G and we say that vn+1 is reachable from v1, writing (v1→vn+1)
Here are some new definitions. A node v in a graph G=(V,E) is called a sink, if for every node w in G that is reachable from vv is also reachable from w. The bottom of a graph is the subset of
all nodes that are sinks, i.e.,bottom(G)={v∈V|∀w∈V:(v→w)⇒(w→v)}. You have to calculate the bottom of certain graphs.

Input

The input contains several test cases, each of which corresponds to a directed graph G. Each test case starts with an integer number v, denoting the number of vertices of G=(V,E), where the vertices will be identified by the integer
numbers in the set V={1,...,v}. You may assume that 1<=v<=5000. That is followed by a non-negative integer e and, thereafter, e pairs of vertex identifiers v1,w1,...,ve,we with
the meaning that (vi,wi)∈E. There are no edges other than specified by these pairs. The last test case is followed by a zero.

Output

For each test case output the bottom of the specified graph on a single line. To this end, print the numbers of all nodes that are sinks in sorted order separated by a single space character. If the bottom is empty, print an empty line.

Sample Input

3 3
1 3 2 3 3 1
2 1
1 2
0

Sample Output

1 3
2

Source

Tarjen缩点统计出度。


#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<cstring>
#include<iostream>
using namespace std;
#define MAXN (5000+10)
#define MAXM (1000000+10)
int n,m,h[MAXN],t[MAXN],dfs[MAXN],tim,kind,s[MAXN],tot;
bool b[MAXN];
int edge[MAXM],next[MAXM],pre[MAXN],size;
int x[MAXM],y[MAXM],numk[MAXN];
void addedge(int u,int v)
{
	edge[++size]=v;
	next[size]=pre[u];
	pre[u]=size;
}
void tar(int u)
{
	dfs[u]=t[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++;
		while (s[tot]!=u) h[s[tot--]]=kind,numk[kind]++;
		h[s[tot--]]=kind;numk[kind]++;

	}
}
int outdegree[MAXN];
int main()
{
	while (scanf("%d",&n)&&n)
	{
		scanf("%d",&m);
		tot=size=tim=kind=0;
		memset(h,0,sizeof(h));
		memset(t,0,sizeof(t));
		memset(dfs,0,sizeof(dfs));
		memset(s,0,sizeof(s));
		memset(pre,0,sizeof(pre));
		memset(b,0,sizeof(b));
		memset(numk,0,sizeof(numk));
		memset(outdegree,0,sizeof(outdegree));

		for (int i=1;i<=m;i++)
		{
			scanf("%d%d",&x[i],&y[i]);
			addedge(x[i],y[i]);
		}
		for (int i=1;i<=n;i++) if (!b[i]) tar(i);
//		for (int i=1;i<=n;i++) cout<<h[i]<<' ';cout<<endl;
		for (int i=1;i<=m;i++)
		{
			if (h[x[i]]^h[y[i]]) outdegree[h[x[i]]]++;
		}
		/*
		int ans=0;
		for (int i=1;i<=kind;i++)
			if (!outdegree[i]) ans+=numk[i];
		cout<<ans<<endl;
		*/
		bool flag=0;
		for (int i=1;i<=n;i++)
			if (!outdegree[h[i]])
			{
				if (flag) printf(" ");else flag=1;printf("%d",i);
			}


	//	cout<<ans<<endl;
		cout<<endl;
	}
	return 0;
}

稳定性(单向图tarjen)

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

【题目描述】

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

第i*2-1个装置通过单向导线第i*2个装置输送能量(它们称为第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(2*i-1,2*i);
	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;
}

POJ 2942(Tarjen的点双连通分量+交叉染色法)

这题是点双连通分量,我一开始写成边的……

首先点双连通分量可能重叠……(1,2) (2,3) (3,1) (3,4) (4,5) (5,6) (3.6)

这时有(1,2,3)和(3,4,5,6)两组双连通分量

故一定要在Tarjen里判……另外Stack存边时注意特判(Stack不能为空)

当dfs[k]<=low[i] 时 就找到了点双连通分量 (这是点双连通)

请注意在推送(k,i)后遍历得到的一堆边(包括(k,i))组成了一组点双连通分量

两个重要定理:

(1)       如果一个双连通分量内的某些顶点在一个奇圈中(即双连通分量含有奇圈),那么这个双连通分量的其他顶点也在某个奇圈中;

(2)       如果一个双连通分量含有奇圈,则他必定不是一个二分图。反过来也成立,这是一个充要条件。

Program P2942;
const
   maxn=1050;
   maxm=1000000;
Var
   n,m,i,j,x,y:longint;
   b:array[1..maxn,1..maxn] of boolean;

   color,c,dfs,low:array[1..maxn] of longint;

   attend,flag:array[1..maxn] of boolean;

   size,time,totssc:longint;

   stack:array[0..maxm,1..2] of longint;

function min(a,b:longint):longint;
begin
   if a<b then exit(a) else exit(b);
end;
function is_Binary(k,col:longint):boolean;
var
   i,j:longint;
begin
   color[k]:=col;
   for i:=1 to n do
      if (flag[i]) and (b[k,i]) then
      begin
         if color[i]=0 then
         begin
            if not(is_binary(i,3-col)) then exit(false);
         end
         else
         if color[k]=color[i] then exit(false);
      end;

   exit(true);
end;

procedure tarjen(k,father:longint);
var
   i,j:longint;
begin
   inc(time);
   dfs[k]:=time;
   low[k]:=time;

   c[k]:=1;
   for i:=1 to n do
      if (b[k,i]) and (dfs[k]>dfs[i]) and (i<>father) then
      begin
         if dfs[i]=0 then
         begin

         inc(size);
         stack[size,1]:=k;
         stack[size,2]:=i;



         tarjen(i,k);
         low[k]:=min(low[k],low[i]);

         if dfs[k]<=low[i] then
         begin
            fillchar(flag,sizeof(flag),false);
            fillchar(color,sizeof(color),false);
            while (size>0) do
            begin
               flag[stack[size,1]]:=true;
               flag[stack[size,2]]:=true;
               dec(size);
               if (stack[size+1,1]=k) and (stack[size+1,2]=i) then break;

            end;

            if not(is_binary(k,1)) then
            begin
               for j:=1 to n do
                  if flag[j] then attend[j]:=true;


            end;


         end;


         end
         else
         if c[i]=1 then low[k]:=min(low[k],dfs[i]);
      end;





   c[k]:=2;

end;


function main:longint;
var
   i,j,tot:longint;
begin
   fillchar(dfs,sizeof(dfs),0);
   fillchar(low,sizeof(low),0);
   fillchar(c,sizeof(c),0);
   fillchar(attend,sizeof(attend),false);
   fillchar(flag,sizeof(flag),false);
   fillchar(color,sizeof(color),0);
   fillchar(stack,sizeof(stack),0);
   size:=0;time:=0;
   for i:=1 to n do
      if (dfs[i]=0) then
      begin
          tarjen(i,0);
      end;

   tot:=0;
   for i:=1 to n do if attend[i] then inc(tot);
   exit(n-tot);

end;

begin
   while not seekeof do
   begin
      read(n,m);
      if (n=0) and (m=0) then break;
      fillchar(b,sizeof(b),true);
      for i:=1 to n do b[i,i]:=false;
      for i:=1 to m do
      begin
         read(x,y);
         b[x,y]:=false;
         b[y,x]:=false;
      end;
      writeln(main);
   end;
end.

POJ 2186(有向图的强连通分量)

题目大意:给有向图G,求图G中有多少点能从所有起点到达

暴搜必T,故本题需要用Tarjen求有向图的强连通分量。

缩点后得DAG(若有环则属同一强连通分量)

由于无环,故这图为树或树的森林

先判断图是否连通,若为森林则无解

否则,判定每个SSC是否有连出的边(由于图无环,故连出的边上的点无法回去)

答案即为出度为0的连通分量上的点

如果不止一个这样的点,则不同的点无法互相到达

Program P2186;
const
   maxn=10000;
   maxm=50000;
var
   head,edge,tail:array[1..maxm] of longint;
   sizeedge:longint;


   n,m,i,j,x,y:longint;
   ssc,c,dfs,low,outdegree,stack:array[1..maxn] of longint;
   time,size:longint;
   totssc:longint;

procedure addedge(u,v:longint);
begin
   inc(sizeedge);
   edge[sizeedge]:=v;
   tail[sizeedge]:=head[u];
   head[u]:=sizeedge;

end;


function min(a,b:longint):longint;
begin
   if a<b then exit(a) else exit(b);
end;
procedure tarjen(k,father:longint);
var
   i,j,p:longint;
begin
   inc(time);
   dfs[k]:=time;low[k]:=time;
   c[k]:=1;
   inc(size);stack[size]:=k;

   p:=head[k];
   while (p<>0) do
   begin
      i:=edge[p];

      if (dfs[k]>dfs[i]) then
      begin
         if c[i]=0 then
         begin
            tarjen(i,k);
            low[k]:=min(low[k],low[i]);
         end
         else if c[i]=1 then low[k]:=min(low[k],dfs[i]);
      end;
      p:=tail[p];

   end;
   if low[k]=dfs[k] then
   begin
      inc(totssc);
      repeat
         i:=stack[size];
         dec(size);
         c[i]:=2;
         ssc[i]:=totssc;
      until ((size=0) or (i=k));

   end;
end;
function main:longint;
var
   i,j,tot,node,p:longint;
begin
   fillchar(dfs,sizeof(dfs),0);
   fillchar(low,sizeof(low),0);
   fillchar(c,sizeof(c),0);
   fillchar(outdegree,sizeof(outdegree),0);
   time:=0;
   totssc:=0;
   for i:=1 to n do
      if (dfs[i]=0) then
      begin
         fillchar(stack,sizeof(stack),0);
         size:=0;
         tarjen(i,0);
      end;

   for i:=1 to n do
   begin
      p:=head[i];
      while (p<>0) do
      begin
         j:=edge[p];

         if (ssc[i]<>ssc[j]) then
         begin
            inc(outdegree[ssc[i]]);
         end;
         p:=tail[p];


      end;
   end;

   node:=0;
   for i:=1 to totssc do
      if outdegree[i]=0 then
      begin
         if node<>0 then exit(0);
         node:=i;
      end;
   tot:=0;
   for i:=1 to n do
      if ssc[i]=node then inc(tot);
   exit(tot);


end;
begin
   sizeedge:=0;
   fillchar(head,sizeof(head),0);
   fillchar(tail,sizeof(tail),0);
   fillchar(edge,sizeof(edge),0);
   read(n,m);
   for i:=1 to m do
   begin
      read(x,y);
      addedge(x,y);
   end;
   writeln(main);
end.

POJ 3177(带重边的连通图的双连通分量)

题目大意:求带重边的连通图至少加几条边变成双连通图

POJ 3352
+重边

用邻接矩阵的表示无压力

Program P3177;
const
   maxn=1000;
   maxm=1000;
var
   n,m,i,j,x,y:longint;
   b:array[1..maxn,1..maxn] of boolean;

   indegree,c,a,low:array[1..maxn] of longint;
   time:longint;
function min(a,b:longint):longint;
begin
   if a<b then exit(a) else exit(b);
end;
function max(a,b:longint):longint;
begin
   if a>b then exit(a) else exit(b);
end;
procedure tarjan(k,father:longint);
var
   i,j:longint;
begin
   inc(time);
   a[k]:=time;
   low[k]:=time;


   c[k]:=1;

   for i:=1 to n do
   begin
      if (b[i,k]) and (i<>father) and (a[i]<a[k]) then
      begin


         if c[i]=0 then
         begin
            tarjan(i,k);
            low[k]:=min(low[k],low[i]);
         end;
         if (c[i]=1) and (i<>father) then
         begin
            low[k]:=min(low[k],a[i]);
         end;


      end;
   end;




   c[k]:=2;



end;

procedure main;
var
   i,j,tot:longint;
begin
   fillchar(a,sizeof(a),0);
   fillchar(low,sizeof(low),0);
   fillchar(c,sizeof(c),0);
   fillchar(indegree,sizeof(indegree),0);

   time:=0;
   tarjan(1,0);

   for i:=1 to n do
      for j:=i+1 to n do
         if (low[i]<>low[j]) and (b[i,j]) then
         begin
            inc(indegree[low[i]]);
            inc(indegree[low[j]]);
         end;
   tot:=0;
   for i:=1 to n do if indegree[i]=1 then inc(tot);
   writeln((tot+1) div 2);

end;

begin
   fillchar(b,sizeof(b),false);
   read(n,m);
   for i:=1 to m do
   begin
      read(x,y);
      b[x,y]:=true;
      b[y,x]:=true;
   end;
   main;
end.

POJ 3352(Tarjen中Low的性质)

这题做了半天……结果发现自己缩点错了……

言归正传,这题给了一个无向图G,求添加几条边后双连通……

做了一上午Tarjen不对……Low就是不满足性质(后来发现这是无向图的,要用有向图版本……——用有向图法做无向图……)

终于……做完了(请忽略Stack,我最后索性直接用Low值了……勉强算hash?)

Program P3352;
const
   maxn=1000;
   maxm=1000;
var
   n,m,i,j,x,y:longint;
   b:array[1..maxn,1..maxn] of boolean;

   indegree,c,stack,a,low:array[1..maxn] of longint;
   size,time:longint;

function min(a,b:longint):longint;
begin
   if a<b then exit(a) else exit(b);
end;
function max(a,b:longint):longint;
begin
   if a>b then exit(a) else exit(b);
end;
procedure swap(a,b:longint);
var
   p:longint;
begin
   p:=a;
   a:=b;
   b:=p;
end;

procedure tarjan(k,father{,deep}:longint);
var
   i,j:longint;
begin

   inc(size);
   stack[size]:=k;     //for suo_dian^_^
   inc(time);
   a[k]:=time;
   low[k]:=time;
 {
   low[k]:=deep;
   a[k]:=deep;
  }

   c[k]:=1;

   for i:=1 to n do
   begin
      if (b[i,k]) and (i<>father) and (a[i]<a[k]) then
      begin


         if c[i]=0 then
         begin
            tarjan(i,k{,deep+1});
            low[k]:=min(low[k],low[i]);
         end;
         if (c[i]=1) and (i<>father) then
         begin
            low[k]:=min(low[k],a[i]);
         end;


      end;
   end;




   c[k]:=2;



end;

procedure main;
var
   i,j,tot:longint;
begin
   fillchar(stack,sizeof(stack),0);
   fillchar(a,sizeof(a),0);
   fillchar(low,sizeof(low),0);
   fillchar(c,sizeof(c),0);
   fillchar(indegree,sizeof(indegree),0);

   size:=0;time:=0;
   tarjan(1,0{,1});

   for i:=1 to n do
      for j:=i+1 to n do
         if (low[i]<>low[j]) and (b[i,j]) then
         begin
            inc(indegree[low[i]]);
            inc(indegree[low[j]]);
         end;
   tot:=0;
   for i:=1 to n do if indegree[i]=1 then inc(tot);
   writeln((tot+1) div 2);

end;

begin
while not seekeof do
begin
   fillchar(b,sizeof(b),false);
   read(n,m);
   for i:=1 to m do
   begin
      read(x,y);
      b[x,y]:=true;
      b[y,x]:=true;
   end;
   main;
end;
end.