学步园

给出一张图问是不是强连通

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
using namespace std;
#define N 500

struct node{
	int from, to, nxt;
}edge[N * 2];

int head[N];
char l[N], h[N];
int m, n, tot;
int low[N], dfn[N], block[N];
vector<int> v[N];	//该连通子图内的点
int edgenum, all;
bool instack[N];
int stack[N], top, Time;

 void init()
 {
 	memset(head, -1, sizeof(head));
 	top = 0, edgenum = 0, tot = 0;
 	memset(instack, 0, sizeof(instack));
 	memset(dfn, 0, sizeof(dfn));
 }
 
 void addedge(int from, int to)
 {
 	edge[edgenum].to = to;
 	edge[edgenum].nxt = head[from];
 	head[from] = edgenum ++;
 }
 
 int gethash(int x, int y)
 {
 	return (x - 1) * m + y;
 }
 
 void tarjan(int u)
 {
 	low[u] = dfn[u] = ++Time;
 	stack[top++] = u;
 	instack[u] = u;
 	
 	for(int i = head[u]; ~i; i = edge[i].nxt)
 	{
 		int v = edge[i].to;
 		if(!dfn[v])
 		{
 			tarjan(v);
 			low[u] = min(low[u], low[v]); 
 		}
 		else if(instack[v])
 		{
 			low[u] = min(low[u], dfn[v]);
 		}
 	}
 	
 	if(low[u] == dfn[u])
 	{
 		int now;  
        tot ++ ; v[tot].clear();  
        do{  
            now = stack[-- top] ;  
            instack[now] = 0 ;  
            block [now] = tot ;  
            v[tot].push_back(now);  
        }while(now != u) ; 
 	}
 }
 
 void tarjan_init(int all)
 {
 	Time = 0;
	for(int i = 1; i <= all; i++)
	{
		if(!dfn[i])
			tarjan(i);
	} 
 }
 
 bool solve()
 {
 	init();
 	for(int i = 1; i <= n; i++)
 	{
 		for(int j = 1; j <= m; j++)
 		{
 			if(l[j] == '^' && i - 1 >= 1)  
	            addedge(gethash(i, j), gethash(i-1, j));  
	        if(l[j] == 'v' && i + 1 <= n)  
	            addedge(gethash(i,j), gethash(i+1,j));  
	        if(h[i] == '<' && j - 1 >= 1)  
	            addedge(gethash(i, j), gethash(i, j-1));  
	        if(h[i] == '>' && j + 1 <= m)  
	            addedge(gethash(i, j), gethash(i, j+1)); 
 		}
 	}
 	all = n * m;
 	tarjan_init(all);
 	return tot <= 1;		//tot联通块数 
 }
 
 int main()
 {
 	while(~scanf("%d%d", &n, &m))
 	{
 		scanf("%s", h+1);
 		scanf("%s", l+1);
 		printf("%s\n", solve() ? "YES": "NO");
 	}
 	return 0;
 }

http://blog.csdn.net/qq574857122/article/details/39827007

套九爷模板一份