首页 > 代码库 > 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 强连通裸题