Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

用不了c++11 iota()与lambda语句第一次korasaju纪念一下

Posted by 983543692 at 2016-05-27 20:51:18 on Problem 2186
/*Korasaju算法求有向图强连通分支
 procedure Strongly_Connected_Components(G);
 begin
 1.深度优先遍历G,算出每个结点u的结束时间f[u],起
点如何选择无所谓。
 2.深度优先遍历G的转置图G T ,选择遍历的起点时,
按照结点的结束时间从大到小进行。遍历的过程中,
一边遍历,一边给结点做分类标记,每找到一个新的
起点,分类标记值就加1。
 3. 第2步中产生的标记值相同的结点构成深度优先森
林中的一棵树,也即一个强连通分量
 end*/
#include<iostream>
#include<stack>
#include<vector>
#include<algorithm>
using namespace std;
typedef pair<int,int> cline;
vector<cline> myline;
const int maxn=10010;
vector<vector<int>> G(maxn);
vector<vector<int>> GT(maxn);
int dfn[maxn]={},becolor[maxn]={},colorout[maxn]={},p[maxn]={};
int index=1,color=1,n,m;
bool cmp(int x,int y)
{
	return dfn[x]>dfn[y];
}
void dfs(int u,bool x); 
void Korasaju()
{
	for(int i=1;i<=n;i++)
	{
		if(!dfn[i])dfs(i,false);
	}
	for(int i=0;i<=n;i++)p[i]=i;
	sort(p+1,p+n+1,cmp);
	for(int i=1;i<=n;i++)
	{
		if(!becolor[p[i]])
		{
			dfs(p[i],true);
			color++;
		}
	}
}
void dfs(int u,bool isT)
{
	if(isT)
	{
		becolor[u]=color;
		for(int i=0;i<GT[u].size();i++)
		{
			int v=GT[u][i];
			if(!becolor[v])dfs(v,true);
		}
	}
	else
	{
		dfn[u]=index;
	    for(int i=0;i<G[u].size();i++)
	    {
		    int v=G[u][i];
		    if(!dfn[v])dfs(v,false);
	    }
	    dfn[u]=++index;
    }
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		G[u].push_back(v);
		GT[v].push_back(u);
		myline.push_back(cline(u,v));
	}
	Korasaju();
	for(int i=0;i<myline.size();i++)
	{
		int u=myline[i].first,v=myline[i].second;
		if(becolor[u]!=becolor[v])colorout[becolor[u]]++;
	}
	int colorsign=0;
	int colorc=0;
	for(int i=1;i<color;i++)
	{
		if(!colorout[i])
		{
			colorsign=i;
			colorc++;
		}
	}
	int result=0;
	for(int i=1;i<=n;i++)if(becolor[i]==colorsign)result++;
	if(colorc==1)printf("%d",result);
	else printf("0");
}
/*
input
3 3
1 2
2 3
3 1

3 3
1 2
2 1
2 3

5 4
1 4
2 4
3 4
5 4

5 5
1 2
2 3
3 1
1 4
4 5

5 6
1 2
2 3
3 1
1 4
4 5
5 3

2 2
1 2
2 1

3 2
1 2
2 1

6 6
1 2
2 3
3 1
1 4
4 5
5 3

5 6
1 2
2 3
3 1
1 4
4 5
5 4

5 7
4 1
1 2
2 3
3 1
1 4
4 5
5 4

5 6
1 2
2 3
3 1
1 4
4 5	
5 1

7 9
1 2
2 3
3 1
4 5
5 6
6 4
4 7
7 1
1 7

6 6
1 2
2 3
3 1
4 5
5 6
6 4

4 4
1 2
2 3
3 1
1 4

4 4
1 2
2 3
3 1
4 1

5 6
1 2
2 3
3 1
5 1
5 4
3 4

7 9
1 2
2 3
3 1
5 1
5 4
3 4
4 7
7 6
6 4

output
3
1
1
1
5
2
0
0
2
5
5
4
0
1
3
1
3*/

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator