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

Re:我的更暴力,看看我的强连通分量+传递闭包

Posted by ccc000111 at 2017-03-23 09:12:33 on Problem 2762
In Reply To:我的更暴力,看看我的强连通分量+传递闭包 Posted by:qq2308091457 at 2016-08-20 16:17:15
> #include<iostream>
> #include<cstdio>
> using namespace std;
> int map[1002][1002],low[1002],dfn[1002],dfdeep,visit[1002];
> int Z[1002],head,cur[1002];
> int tree[1000][1000],belong[1002];
> int n,m,T,num;
> void init()
> {
> 	int i,j;
> 	for(i=1;i<=n;i++)
> 	{
> 		visit[i]=dfn[i]=low[i]=cur[i]=belong[i]=0;
> 		for(j=1;j<=n;j++)
> 			map[i][j]=tree[i][j]=0;
> 	}
> 	num=0;
> 	for(i=1;i<=m;i++)
> 	{
> 		int x,y;
> 		scanf("%d%d",&x,&y);
> 		map[x][y]=1;
> 	}
> }
> void dfs(int x)
> {
> 	int i;
> 	head++;
>     Z[head]=x;
> 	cur[x]=1;
> 	visit[x]=1;
> 	dfdeep++;
> 	low[x]=dfn[x]=dfdeep;
> 	for(i=1;i<=n;i++)
> 		if(map[x][i])
> 			if(!visit[i])
> 			{
> 				dfs(i);
> 				if(low[i]<low[x])
> 					low[x]=low[i];
> 			}
> 			else
> 				if(cur[i])
> 					if(dfn[i]<low[x])
> 						low[x]=dfn[i];
> 	if(low[x]==dfn[x])
> 	{
> 		num++;
> 		while(1)
> 		{
> 			if(head<0)
> 				break;
> 			int v=Z[head];
> 			head--;
> 			belong[v]=num;
> 			cur[v]=0;
> 			if(v==x)
> 				break;
> 		}
> 	}
> }
> int main()
> {
> 	scanf("%d",&T);
> 	while(T--)
> 	{
> 		scanf("%d%d",&n,&m);
> 		init();
> 		int i,j;
> 		for(i=1;i<=n;i++)
> 			if(!dfn[i])
> 			{
> 				head=-1;
> 				dfs(i);
> 				if(head>=0)
> 				{
> 					num++;
> 					while(1)
> 					{
> 						if(head<0)
> 							break;
> 			     		int v=Z[head];
> 				    	head--;
> 				    	belong[v]=num;
> 					}
> 				}
> 			}
> 		int length=0;
> 		for(i=1;i<=n;i++)
> 			for(j=1;j<=n;j++)
> 				if(map[i][j]&&belong[i]!=belong[j])
> 					tree[belong[i]][belong[j]]=1;
> 		int k;
> 		for(k=1;k<=num;k++)
> 			for(i=1;i<=num;i++)
> 				if(tree[i][k])
> 					for(j=1;j<=num;j++)
> 						if(tree[k][j])
> 							tree[i][j]=true;
> 		int flag=1;
> 		for(i=1;i<=num;i++)
> 			for(j=1;j<=num;j++)
> 				if(!tree[i][j]&&!tree[j][i]&&i!=j)
> 					flag=0;
> 		if(flag)
> 			printf("Yes\n");
> 		else
> 			printf("No\n");
> 	}
> 	return 0;
> }
> 
> 
> 
> 
然后就哇了。。。。。。

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