阿祁的部落格

CodeForces Round #490 E 解題心得( 題目 )

解題概念:graph、連通塊

解題方法:主要是最近多做了新bot，可以拿來打模擬cf競賽，其中看到一題不錯的，這題就是帶入SCC，接著特別判斷即可。但後來發現有別的方法，好像拓樸就好了。

//Author:En Chi Tsung(欉恩祁)

//Date:2022/05/25

import java.util.*;

import java.io.*;

import java.math.BigInteger;

public class Main {

    public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

    public static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));

    public static long ret;

    public static int reti,rd,N,ans=0,xx,yy,o,t=0,no=1;

    public static final int mod=998244353;

    public static boolean neg;

    public static int[] w=new int[5005];


    public static int[] out=new int[5005];

    public static boolean[] ins=new boolean[5005];

    public static int[] dfs=new int[5005];

    public static int[] low=new int[5005];

    public static int[] scc=new int[5005];

    public static Stack<Integer> st=new Stack<>();

    public static ArrayList<ArrayList<Integer>> e=new ArrayList<>();

    public static ArrayList<ArrayList<Integer>> ne=new ArrayList<>();

    public static void main(String[] args) throws Exception{

        final int n=readint();

        for(int i=0;i<=n;i++) {

            e.add(new ArrayList<Integer>());

            ne.add(new ArrayList<Integer>());

        }

        final int m=readint();

        final int s=readint();

        int x,y;

        for(int i=0;i<m;i++) {

            x=readint();

            y=readint();

            e.get(x).add(y);

        }

        for(int i=1;i<=n;i++) {

            if(dfs[i]==0) {

                tarjan(i);

                st.clear();

            }

        }

        for(int i=1;i<=n;i++) {

            for(int j:e.get(i)) {

                if(scc[i]==scc[j]) {

                    continue;

                }

                ne.get(scc[j]).add(scc[i]);

                out[scc[i]]++;

            }

        }

        

        for(int i=1;i<no;i++) {

            if(i==scc[s])continue;

            //System.out.println(ans);

            if(ne.get(i).size()==0)ans++;

        }

        System.out.println(ans);

    }

    

    public static void tarjan(int x) {

        dfs[x]=low[x]=++t;

        ins[x]=true;

        st.push(x);

        for(int i:e.get(x)) {

            if(dfs[i]==0) {

                tarjan(i);

                low[x]=Math.min(low[x],low[i]);

            }

            else if(ins[i]) {

                low[x]=Math.min(low[x],dfs[i]);

            }

        }

        if(!ins[x])return;

        if(dfs[x]==low[x]) {

            while(true) {

                o=st.pop();

                ins[o]=false;

                scc[o]=no;

                if(o==x)break;

            }

            no++;    

        }

        ins[x]=false;

    }



 

    public static int readint() throws Exception{

        reti=0;

        while(rd<48||rd>57) {

            rd=br.read();

        }

        while(rd>47&&rd<58) {

            reti*=10;

            reti+=(rd&15);

            rd=br.read();

        }

        return reti;

    }

    public static long readlong() throws Exception{

        ret=0;

        while(rd<48||rd>57) {

            rd=br.read();

        }

        while(rd>47&&rd<58) {

            ret*=10;

            ret+=(rd&15);

            rd=br.read();

        }

        return ret;

    }

}