Java(javac 1.8) 解法, 执行用时: 90ms, 内存消耗: 18808K, 提交时间: 2021-03-16 17:19:53
import java.io.*;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.RoundingMode;
import java.text.DecimalFormat;
import java.util.*;
public class Main {
static class Task {
public static String roundS(double result, int scale){
String fmt = String.format("%%.%df", scale);
return String.format(fmt, result);
// DecimalFormat df = new DecimalFormat("0.000000");
// double result = Double.parseDouble(df.format(result));
}
// 有向图的强连通分量,非递归
void tarjanStack(int u) {
int stk[] = new int[100001];
int p =1; stk[0] = u;
ot:while(p>0) {
u = stk[p-1];
if (dfn[u] == 0) {
low[u] = dfn[u] = ++time;
stack[top++] = u;
}
// remember h will be changed after using it
for (; h[u] != -1; h[u] = ne[h[u]]) {
int v = to[h[u]];
if (dfn[v] == 0) {
stk[p++] = v;
continue ot;
// low[u] = Math.min(low[u], low[v]);
} else if (sccno[v] == 0) {
// dfn>0 but sccno==0, means it's in current stack
low[u] = Math.min(low[u], low[v]);
}
}
p--;
if (dfn[u] == low[u]) {
sccno[u] = ++scc_cnt;
cnt[scc_cnt]++;
while (stack[top - 1] != u) {
sccno[stack[top - 1]] = scc_cnt;
--top;
cnt[scc_cnt]++;
}
--top;
}
if(p>=1){
int fa = stk[p-1];
low[fa] = Math.min(low[fa], low[u]);
}
}
}
int[] h,ne,to;
int dfn[],low[],stack[],cnt[];
int sccno[];
boolean iscut[];
int time = 0,top = 0;
int scc_cnt;int ct = 0;
int root = 0;
void add(int u,int v){
to[ct] = v;
ne[ct] = h[u];
h[u] = ct++;
}
int[] h1,to1,ne1;
int ct1 = 0;
public void solve(int testNumber, InputReader in, PrintWriter out) {
int t= in.nextInt();
while(t-->0) {
int n = in.nextInt();
int m = in.nextInt();
ct = 0;
scc_cnt = 0;
h = new int[n + 1];
Arrays.fill(h, -1);
h1 = new int[n + 1];
Arrays.fill(h1, -1);
{
ne = new int[m];
to = new int[m];
to1 = new int[m];
ne1 = new int[m];
}
{
dfn = new int[n + 1];
low = new int[n + 1];
stack = new int[n + 1];
sccno = new int[n + 1];
cnt = new int[n + 1];
}
for (int j = 0; j < m; ++j) {
int u = in.nextInt();
int v = in.nextInt();
add(u, v);
}
int hh[] = h.clone();
for (int i = 1; i <= n; i++) {
if (dfn[i] == 0) tarjanStack(i);
}
int du[] = new int[scc_cnt + 1];
h1 = new int[scc_cnt + 1];
Arrays.fill(h1, -1);
to1 = new int[m];
ne1 = new int[m];
// scc_cnt 个点
h = hh;
ct1 = 0;
for (int i = 1; i <= n; i++) {
for (int j = h[i]; j != -1; j = ne[j]) {
int y = to[j];
if (sccno[i] != sccno[y]) {
// add(sccno[i],sccno[y]); // 建新图
to1[ct1] = sccno[y];
ne1[ct1] = h1[sccno[i]];
h1[sccno[i]] = ct1++;
du[sccno[y]]++; //存入度
}
}
}
int q[] = new int[scc_cnt + 1];
int end = 0;
int st = 0;
int dp[] = new int[scc_cnt + 1];
long k = 0;
long ans = 0;
for (int i = 1; i <= scc_cnt; ++i) {
if (du[i] == 0) {
q[end++] = i;
dp[i] = 1;
break;
}
}
while (st < end) {
int cur = q[st++];
for (int i = h1[cur]; i != -1; i = ne1[i]) {
int y = to1[i];
dp[y] = 1;
if (--du[y] == 0) {
q[end++] = y;
}
break;
}
}
boolean ok = true;
for (int i = 1; i <= scc_cnt; ++i) {
if (dp[i] == 0) {
ok = false;
}
}
out.println(ok?"Yes":"No");
}
}
// int t = in.nextInt();
// int n = in.nextInt();
// int m = in.nextInt();
//
// ct = 0;
// h = new int[n];Arrays.fill(h,-1);
// if(t==1) {
// to = new int[m * 2];
// ne = new int[m * 2];
//
// fob = new boolean[m * 2];
// }else{
// to = new int[m];
// ne = new int[m];
//
// }
//
//
// int rd[] = new int[n];
// int cd[] = new int[n];
// li = new int[m];
// tp = m-1;
//
// int rt= 0;
//
// for(int i=0;i<m;++i){
// int u = in.nextInt()-1;
// int v = in.nextInt()-1;
// add(u,v);
// if(t==1){
// add(v,u);
// }
// cd[u]++;
// rd[v]++;
// rt = u;
// }
//
// if(t==2){
//
// for(int i=0;i<n;++i){
// if(rd[i]!=cd[i]){
// out.println("NO");return;
// }
// }
// }else{
//
// for(int i=0;i<n;++i){
// if(((rd[i]+cd[i])%2)>0){
// out.println("NO");return;
// }
// }
//
// }
//
//
//
// dfs11(rt, t);
//
//
//
// if(tp!=-1){
// out.print("NO");
// return;
// }
//
// out.println("YES");
//
// for(int i=0;i<m;++i){
// out.print(li[i]+ " ");
// }
// int f1[][] = new int[q][3];
//
// for(int i=0;i<q;++i){
// for(int j=0;j<3;++j){
// f1[i][j] = in.nextInt();
// }
// }
//
//
// int h[] = new int[n+1];
//
// Arrays.fill(h,-1);
//
//
// int ne[] = new int[p*2+q];
// int to[] = new int[p*2+q];
// int wt[] = new int[p*2+q];
// ct = 0;
// Func fk = (int x,int y,int z) -> {
// to[ct] = y;
// ne[ct] = h[x];
// wt[ct] = z;
// h[x] = ct++;
// };
//
// for(int i=0;i<p;++i){
// int u = f[i][0];
// int v = f[i][1];
//
//
//
//
// fk.add(u,v,f[i][2]);
// fk.add(v,u,f[i][2]);
// }
//
// for(int i=0;i<q;++i){
// int u = f1[i][0];
// int v = f1[i][1];
//
//
//
//
// fk.add(u,v,f1[i][2]);
// }
// int dp[] = new int[n+1];
// Arrays.fill(dp,100000000);
// dp[s] = 0;
//
//
// PriorityQueue<int[]> qu = new PriorityQueue<>(Comparator.comparingInt((x)->x[0]));
// qu.add(new int[]{0,s});
// while(qu.size()>0){
// int cc[] = qu.poll();
// int cur = cc[1];
// if(cc[0]!=dp[cur]) continue;
// for(int j = h[cur];j!=-1;j=ne[j]){
// int v = to[j];
// if(dp[v] > dp[cur] + wt[j]){
// dp[v] = dp[cur] + wt[j];
// qu.offer(new int[]{dp[v],v});
// }
// }
// }
//
// for(int j=1;j<=n;++j){
// if(dp[j]==100000000){
// out.println("NO PATH");
// }else{
// out.println(dp[j]);
// }
// }
// for(int t=0;t<5;++t) {
// int at = fi[t];
// dp[at][t] = 0;
// PriorityQueue<int[]> q = new PriorityQueue<>(Comparator.comparingInt((x) -> x[0]));
// q.offer(new int[]{0, at});
// while (q.size() > 0) {
// int cur[] = q.poll();
// if (cur[0] != dp[cur[1]][t]) continue;
// int i = cur[1];
// for (int j = h[i]; j != -1; j = ne[j]) {
// int v = to[j];
// if (dp[i][t] + wt[j] < dp[v][t]) {
// dp[v][t] = dp[i][t] + wt[j];
// q.offer(new int[]{dp[v][t], v});
// }
// }
// }
// }
// int cl[] = new int[]{0,1,2,3,4};
// int rs = Integer.MAX_VALUE;
// do{
// int s= dp[1][cl[0]];
// for(int j=0;j<4;++j){
// int nxt = fi[cl[j+1]];
// s += dp[nxt][cl[j]];
// }
// rs = Math.min(rs,s);
//
//
// }while(next_perm(cl));
//
// out.print(rs);
boolean next_perm(int[] a){
int len = a.length;
for(int i=len-2,j = 0;i>=0;--i){
if(a[i]<a[i+1]){
j = len-1;
for(;a[j]<=a[i];--j);
int p = a[j];
a[j] = a[i];
a[i] = p;
j = i+1;
for(int ed = len-1;j<ed;--ed) {
p = a[ed];
a[ed] = a[j];
a[j++] = p;
}
return true;
}
}
return false;
}
static long mul(long a, long b, long p) {
long res = 0, base = a;
while (b > 0) {
if ((b & 1L) > 0)
res = (res + base) % p;
base = (base + base) % p;
b >>= 1;
}
return res;
}
static long mod_pow(long k, long n, long p) {
long res = 1L;
long temp = k % p;
while (n != 0L) {
if ((n & 1L) == 1L) {
res = mul(res, temp, p);
}
temp = mul(temp, temp, p);
n = n >> 1L;
}
return res % p;
}
public static double roundD(double result, int scale) {
BigDecimal bg = new BigDecimal(result).setScale(scale, RoundingMode.UP);
return bg.doubleValue();
}
}
private static void solve() {
InputStream inputStream = System.in;
// InputStream inputStream = null;
// try {
// inputStream = new FileInputStream(new File("D:\\chrome_download\\exp.out"));
// } catch (FileNotFoundException e) {
// e.printStackTrace();
// }
OutputStream outputStream = System.out;
// OutputStream outputStream = null;
// File f = new File("D:\\chrome_download\\");
// try {
// f.createNewFile();
// } catch (IOException e) {
// e.printStackTrace();
// }
// try {
// outputStream = new FileOutputStream(f);
// } catch (FileNotFoundException e) {
// e.printStackTrace();
// }
InputReader in = new InputReader(inputStream);
PrintWriter out = new PrintWriter(outputStream);
Task task = new Task();
task.solve(1, in, out);
out.close();
}
public static void main(String[] args) {
// new Thread(null, () -> solve(), "1", (1 << 30)).start();
solve();
}
static class InputReader {
public BufferedReader reader;
public StringTokenizer tokenizer;
public InputReader(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream), 32768);
tokenizer = null;
}
public String nextLine() {
String line = null;
try {
line = reader.readLine();
} catch (IOException e) {
throw new RuntimeException(e);
}
return line;
}
public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
public char nextChar() {
return next().charAt(0);
}
public int[] nextArray(int n) {
int res[] = new int[n];
for (int i = 0; i < n; ++i) {
res[i] = nextInt();
}
return res;
}
public long nextLong() {
return Long.parseLong(next());
}
public double nextDouble() {
return Double.parseDouble(next());
}
}
}
C++(g++ 7.5.0) 解法, 执行用时: 12ms, 内存消耗: 5292K, 提交时间: 2022-08-21 22:04:30
#include <vector>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <stack>
using namespace std ;
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define per(i, a, b) for (int i = a; i >= b; i--)
#define siz(a) (int) a.size()
#define pb push_back
#define mp make_pair
#define ll long long
#define fi first
#define se second
const int N = 100010 ;
int n, m, ans1, ans2, ans3, tot, scc ;
vector <int> e[N] ;
int dfn[N], low[N], ins[N], bl[N], in[N], out[N] ;
stack <int> s ;
void clear() {
tot = 0, ans1 = 0, ans2 = 0, ans3 = 0, scc = 0 ;
memset(dfn, 0, sizeof(dfn)) ;
memset(low, 0, sizeof(low)) ;
memset(ins, 0, sizeof(ins)) ;
memset(bl, 0, sizeof(bl)) ;
memset(in, 0, sizeof(in)) ;
memset(out, 0, sizeof(out)) ;
rep(i, 1, n) e[i].clear() ;
}
void tarjan(int u) {
dfn[u] = low[u] = ++tot ;
ins[u] = 1 ; s.push(u) ;
rep(i, 0, siz(e[u]) - 1) {
int v = e[u][i] ;
if (!dfn[v]) {
tarjan(v) ;
low[u] = min(low[u], low[v]) ;
}
else if (ins[v]) low[u] = min(low[u], dfn[v]) ;
}
if (low[u] == dfn[u]) {
bl[u] = ++scc ;
ins[u] = 0 ;
while (s.top() != u) {
int v = s.top() ;
ins[v] = 0 ;
bl[v] = scc ;
s.pop() ;
}
s.pop() ;
}
}
signed main() {
int t ; scanf("%d", &t) ;
while (t--) {
clear() ;
scanf("%d%d", &n, &m) ;
rep(i, 1, m) {
int a, b ; scanf("%d%d", &a, &b) ;
e[a].pb(b) ;
}
rep(i, 1, n) if (!dfn[i]) tarjan(i) ;
rep(u, 1, n)
rep(j, 0, siz(e[u]) - 1) {
int U = bl[u], V = bl[e[u][j]] ;
if (U != V) in[V]++, out[U]++ ;
}
rep(i, 1, scc) {
if (in[i] == 0 && out[i] >= 1) ans1++ ;
if (in[i] >= 1 && out[i] == 0) ans2++ ;
if (in[i] >= 1 && out[i] >= 1) ans3++ ;
}
if (scc == 1 || (ans1 == 1 && ans2 == 1 && ans1 + ans2 + ans3 == scc)) puts("Yes") ;
else puts("No") ;
}
return 0 ;
}
C++11(clang++ 3.9) 解法, 执行用时: 9ms, 内存消耗: 5244K, 提交时间: 2020-10-14 11:59:27
#include<stack>
#include<vector>
#include<queue>
#include<cstdio>
#include<cstring>
#define ui unsigned int
using namespace std;
const int M=100500;
int dfn[M],vis[M],fa[M],low[M];
int ind,ti,in[M];
int n,m;
vector<int>v[M];
vector<int>G[M];
stack<int>s;
void tarjan(int x)
{
low[x]=dfn[x]=++ind;vis[x]=1;s.push(x);
for(ui i=0;i<v[x].size();i++)
{
int go=v[x][i];
if(!dfn[go])
{
tarjan(go);
low[x]=min(low[x],low[go]);
}
else if(vis[go])
low[x]=min(low[x],dfn[go]);
}
if(low[x]==dfn[x])
{
int t=-1;ti++;
while(t!=x)
{
t=s.top();s.pop();
vis[t]=0;fa[t]=ti;
}
}
return ;
}
int top()
{
queue<int>q;int cnt=0;
for(int i=1;i<=ti;i++)
if(!in[i])q.push(i);
if(q.size()>1)return 0;
while(q.size())
{
int u=q.front();q.pop();cnt++;
for(ui i=0;i<G[u].size();i++)
{
int go=G[u][i];
in[go]--;
if(!in[go])q.push(go);
}
if(q.size()>1)return 0;
}
if(cnt!=ti)return 0;
return 1;
}
void clean()
{
ti=ind=0;
for(int i=1;i<=n;i++)
v[i].clear(),G[i].clear(),
in[i]=dfn[i]=low[i]=vis[i]=fa[i]=0;
}
int main()
{
int t,a,b;
for(scanf("%d",&t);t--;)
{
scanf("%d%d",&n,&m);clean();
for(int i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
v[a].push_back(b);
}
for(int i=1;i<=n;i++)
if(!dfn[i])tarjan(i);
for(int i=1;i<=n;i++)
for(ui k=0;k<v[i].size();k++)
{
int go=v[i][k];
if(fa[i]!=fa[go])
G[fa[i]].push_back(fa[go]),in[fa[go]]++;
}
if(top())puts("Yes");
else puts("No");
}
}
, the number of rooms and corridors in the cave. The next m lines each contains two integers u and v, indicating that there is a corridor connecting room u and room v directly.