AcWing 4801. 强连通图
原题链接
中等
作者:
乔治弟弟
,
2023-05-08 21:00:14
,
所有人可见
,
阅读 105
建图 + Floyd
$O(n^4)$
Java 代码
import java.util.*;
import java.io.*;
import java.math.*;
import java.text.*;
public class Main{
static int n,m;
static int N=410;
static boolean[][] g=new boolean[N][N];
public static void main(String[] args) throws Exception{
Read sc=new Read();
n=sc.nextInt();m=sc.nextInt();
String s=sc.next();
for(int i=1;i<=n*m;i++) g[i][i]=true;
for(int i=0;i<n;i++){
char x=s.charAt(i);
int head=i*m+1;
for(int j=0;j<m-1;j++){
int next=head+1;
if(x=='>') g[head][next]=true;
else g[next][head]=true;
head=next;
}
}
s=sc.next();
for(int i=0;i<m;i++){
char x=s.charAt(i);
int head=i+1;
for(int j=0;j<n-1;j++){
int next=head+m;
if(x=='v') g[head][next]=true;
else g[next][head]=true;
head=next;
}
}
for(int k=1;k<=n*m;k++){
for(int i=1;i<=n*m;i++){
for(int j=1;j<=n*m;j++) g[i][j]|=(g[i][k]&&g[k][j]);
}
}
boolean flag=true;
for(int i=1;i<=n*m;i++){
for(int j=1;j<=n*m;j++){
if(!g[i][j]){
flag=false;
break;
}
}
}
if(flag) System.out.println("YES");
else System.out.println("NO");
sc.bw.flush();
sc.bw.close();
}
}
class Read{
BufferedReader bf;
StringTokenizer st;
BufferedWriter bw;
public Read(){
bf=new BufferedReader(new InputStreamReader(System.in));
st=new StringTokenizer("");
bw=new BufferedWriter(new OutputStreamWriter(System.out));
}
public String nextLine() throws IOException{
return bf.readLine();
}
public String next() throws IOException{
while(!st.hasMoreTokens()){
st=new StringTokenizer(bf.readLine());
}
return st.nextToken();
}
public char nextChar() throws IOException{
return next().charAt(0);
}
public int nextInt() throws IOException{
return Integer.parseInt(next());
}
public long nextLong() throws IOException{
return Long.parseLong(next());
}
public double nextDouble() throws IOException{
return Double.parseDouble(next());
}
public float nextFloat() throws IOException{
return Float.parseFloat(next());
}
public byte nextByte() throws IOException{
return Byte.parseByte(next());
}
public short nextShort() throws IOException{
return Short.parseShort(next());
}
public BigInteger nextBigInteger() throws IOException{
return new BigInteger(next());
}
public void println(int a) throws IOException{
bw.write(String.valueOf(a));
bw.newLine();
return;
}
public void print(int a) throws IOException{
bw.write(String.valueOf(a));
return;
}
public void println(String a) throws IOException{
bw.write(a);
bw.newLine();
return;
}
public void print(String a) throws IOException{
bw.write(a);
return;
}
public void println(long a) throws IOException{
bw.write(String.valueOf(a));
bw.newLine();
return;
}
public void print(long a) throws IOException{
bw.write(String.valueOf(a));
return;
}
public void println(double a) throws IOException{
bw.write(String.valueOf(a));
bw.newLine();
return;
}
public void print(double a) throws IOException{
bw.write(String.valueOf(a));
return;
}
public void print(BigInteger a) throws IOException{
bw.write(a.toString());
return;
}
public void print(char a) throws IOException{
bw.write(String.valueOf(a));
return;
}
public void println(char a) throws IOException{
bw.write(String.valueOf(a));
bw.newLine();
return;
}
}