AcWing 3250. 通信网络java
原题链接
中等
作者:
huaqingren
,
2021-03-06 20:35:16
,
所有人可见
,
阅读 351
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main
{
private static int N=1010;
private static List<Integer>[] g1=new ArrayList[N];//java中邻接表
private static List<Integer>[] g2=new ArrayList[N];
private static boolean[] st1=new boolean[N];
private static boolean[] st2=new boolean[N];
private static int n,m;
public static void main(String[] args)
{
Scanner scan=new Scanner(System.in);
n=scan.nextInt();
m=scan.nextInt();
for(int i=1;i<=n;i++)
g1[i]=new ArrayList<>();
for(int i=1;i<=n;i++)
g2[i]=new ArrayList<>();
while(m--!=0)
{
int a=scan.nextInt();
int b=scan.nextInt();
g1[a].add(b);
g2[b].add(a);
}
int res=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
st1[j]=false;
st2[j]=false;
}
dfs(i,g1,st1);
dfs(i,g2,st2);
int cnt=0;
for(int j=1;j<=n;j++)
if(st1[j]||st2[j])
cnt++;
if(cnt==n)
res++;
}
System.out.println(res);
scan.close();
}
private static void dfs(int u, List<Integer>[] g, boolean[] st)
{
st[u]=true;
for(int i=0;i<g[u].size();i++)
{
int t=g[u].get(i);
if(!st[t])
dfs(t,g,st);
}
}
}