首页 > 代码库 > Codeforces 475B Strongly Connected City 强连通裸题
Codeforces 475B Strongly Connected City 强连通裸题
题目链接:点击打开链接
题意:
就是n*m的矩阵,
每行能走的方向
每列能走的方向
问:图是否强连通。
只要4个边界成环即可。
或者无脑tarjan
==
#pragma comment(linker, "/STACK:102400000,102400000") #include <stdio.h> #include <iostream> #include <algorithm> #include <vector> #include <string.h> using namespace std; int haifei; #define N 1000 //N为最大点数 #define M 500*10 //M为最大边数 int n, m; struct Edge{ int from, to, nex; }edge[M<<1]; int head[N], edgenum; void add(int u, int v){//边的起点和终点 Edge E={u, v, head[u]}; edge[edgenum] = E; head[u] = edgenum++; } int DFN[N], Low[N], Stack[N], top, Time; //Low[u]是点集{u点及以u点为根的子树} 中(所有反向弧)能指向的(离根最近的祖先v) 的DFN[v]值(即v点时间戳) int taj;//连通分支标号,从1开始 int Belong[N];//Belong[i] 表示i点属于的连通分支 bool Instack[N]; vector<int> bcc[N]; //标号从1开始 void tarjan(int u ,int fa){ DFN[u] = Low[u] = ++ Time ; Stack[top ++ ] = u ; Instack[u] = 1 ; for (int i = head[u] ; ~i ; i = edge[i].nex ){ int v = edge[i].to ; if(DFN[v] == -1) { tarjan(v , u) ; 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; taj ++ ; bcc[taj].clear(); do{ now = Stack[-- top] ; Instack[now] = 0 ; Belong [now] = taj ; bcc[taj].push_back(now); }while(now != u) ; } } void tarjan_init(int all){ memset(DFN, -1, sizeof(DFN)); memset(Instack, 0, sizeof(Instack)); top = Time = taj = 0; for(int i=1;i<=all;i++)if(DFN[i]==-1 )tarjan(i, i); //注意开始点标!!! } void init(){memset(head, -1, sizeof(head)); edgenum=0;} char h[50],l[50]; int Hash(int x, int y){ return (x-1)*m+y; } bool solve(){ init(); for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) { if(l[j] == '^' && i-1>=1) add(Hash(i,j), Hash(i-1,j)); if(l[j]=='v'&&i+1<=n) add(Hash(i,j), Hash(i+1,j)); if(h[i] == '<' && j-1 >= 1) add(Hash(i,j), Hash(i, j-1)); if(h[i]=='>'&&j+1 <= m) add(Hash(i,j), Hash(i, j+1)); } tarjan_init(n*m); return taj <= 1; } int main(){ while(cin>>n>>m){ scanf("%s", h+1); scanf("%s", l+1); solve() ? puts("YES") : puts("NO"); } return 0; }
Codeforces 475B Strongly Connected City 强连通裸题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。