Java(javac 1.8) 解法, 执行用时: 378ms, 内存消耗: 44940K, 提交时间: 2021-03-16 13:31:00
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], dfn[v]);
}
}
p--;
if (dfn[u] == low[u]) {
sccno[u] = ++scc_cnt;
while (stack[top - 1] != u) {
sccno[stack[top - 1]] = scc_cnt;
--top;
}
--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 n = in.nextInt();
int m = 0;
int cc[][] = new int[n][n];
for(int j=0;j<n;++j){
for(int l=0;l<n;++l) {
cc[j][l] = in.nextInt();
m += cc[j][l];
}
}
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<n;++j){
for(int l=0;l<n;++l) {
if(cc[j][l]==1) {
add(j + 1, l + 1);
}
}
}
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;
Set<Integer> vis[] = new Set[scc_cnt+1];
for(int i=1;i<=scc_cnt;++i){
vis[i] = new HashSet<>();
}
for(int i=1;i<=n;i++) {
cnt[sccno[i]]++;
for(int j=h[i]; j!=-1; j=ne[j]) {
int y = to[j];
// 去掉连接联通分量的重边
if(sccno[i] != sccno[y] && !vis[sccno[i]].contains(sccno[y])) {
vis[sccno[i]].add(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 cdp[] = new long[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] = cnt[i];
cdp[i] = 1;
}
}
out.print(end);
// while(st<end){
// int cur = q[st++];
// if(k<dp[cur]){
// k = dp[cur];
// }
//
//
// for(int i=h1[cur];i!=-1;i=ne1[i]){
// int y = to1[i];
//
//
// // dp[y] += dp[cur];
// if(dp[y]<dp[cur]+ cnt[y]){
// dp[y] = dp[cur]+ cnt[y];
// cdp[y] = cdp[cur];
// }else if(dp[y] == dp[cur]+ cnt[y]){
// cdp[y] += cdp[cur];
// cdp[y] %= xx;
// }
//
// if(--du[y]==0){
// q[end++] = y;
// }
// }
// }
//
// for(int i=1;i<=scc_cnt;++i){
// if(dp[i]==k){
// ans += cdp[i];
// ans %= xx;
// }
// }
//
// out.println(k);
// out.println(ans);
}
// 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++14(g++5.4) 解法, 执行用时: 287ms, 内存消耗: 6436K, 提交时间: 2020-01-05 20:50:26
#include<bits/stdc++.h>
using namespace std;
int N;
int C[1024][1024];
int vis[1024];
int scc[1024];
int scc_cnt;
vector<int> path;
int indeg[1024];
void dfs(int s) {
vis[s] = true;
for (int t = 1; t <= N; t++) if (C[s][t]&&!vis[t]) dfs(t);
path.push_back(s);
}
void rdfs(int s) {
scc[s] = scc_cnt;
for (int t = 1; t <= N; ++t) if (C[t][s]&&!scc[t]) rdfs(t);
}
void Kosaraju() {
for (int i = 1; i <= N; ++i) if (!vis[i]) dfs(i);
reverse(path.begin(), path.end());
for (auto i: path) if (!scc[i]) scc_cnt++, rdfs(i);
}
int main() {
cin >> N;
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= N; ++j) cin >> C[i][j];
}
Kosaraju();
for (int s = 1; s <= N; s++) {
for (int t = 1; t <= N; t++) if (C[s][t] && scc[s] != scc[t]) indeg[scc[t]]++;
}
cout << count(indeg+1, indeg+scc_cnt+1, 0) << endl;
}
C++ 解法, 执行用时: 214ms, 内存消耗: 2556K, 提交时间: 2022-01-17 22:43:10
#include<bits/stdc++.h>
using namespace std;
struct node
{
int to,next;
}si[1010000];
int l=1,n,a,head[10000]={0},tot=0,ans=0;
int flag[10000]={0};
bool f[10000]={0};
void add(int x,int y)
{
tot++;
si[tot].to=y;
si[tot].next=head[x];
head[x]=tot;
}
void dfs(int i)
{
flag[i]=l;
if(!head[i])
return;
for(int j=head[i];j;j=si[j].next)
{
if(flag[si[j].to]!=l)dfs(si[j].to);
if(f[si[j].to])f[si[j].to]=0,ans--;
}
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
cin>>a;
if(a==1)add(i,j);
}
for(int i=0;i<n;i++)
if(!flag[i])
{
l++;
ans++;
dfs(i);
f[i]=1;
}
cout<<ans;
return 0;
}
，则奸细i能将消息直接传递给奸细j。的矩阵（若第I行第J列为1，则奸细I能将消息直接传递给奸细J，若第I行第J列为0，则奸细I不能将消息直接传递给奸细J）。