fork download
copy 
  1. /**
  2.  * Created by ruthless on 27/4/16.
  3.  */
  4.  
  5.  
  6. import java.io.*;
  7. import java.util.*;
  8.  
  9.  
  10. class spoj_cc {
  11.     static LinkedList<Integer>[] list;
  12.     static LinkedList<Integer>[] tlist;
  13.     static boolean visited[];
  14.     static Stack<Integer> ts;
  15.     static int gno;
  16.     static int comp[];
  17.  
  18.     public static void DFS1(int x)
  19.     {
  20.         if(visited[x]) return;
  21.         visited[x]=true;
  22.  
  23.         for(int i=0;i<list[x].size();i++) DFS1(list[x].get(i));
  24.         ts.push(x);
  25.     }
  26.  
  27.     public static void DFS2(int x)
  28.     {
  29.         if(visited[x]) return;
  30.         visited[x]=true;
  31.         for (int i=0;i<tlist[x].size();i++) DFS2(tlist[x].get(i));
  32.         comp[x]=gno;
  33.     }
  34.     public static void main(String args[]) throws IOException {
  35.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  36.         BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
  37.         String[] s=br.readLine().trim().split(" ");
  38.         int v=Integer.parseInt(s[0]);
  39.         int e=Integer.parseInt(s[1]);
  40.         list=new LinkedList[v+1];
  41.         tlist=new LinkedList[v+1];
  42.         visited=new boolean[v+1];
  43.         ts=new Stack<>();
  44.         gno=0;
  45.         comp=new int[v+1];
  46.         for (int i=1;i<=v;i++)
  47.         {
  48.             list[i]=new LinkedList();
  49.             tlist[i]=new LinkedList<>();
  50.         }
  51.         while (e-->0)
  52.         {
  53.             s=br.readLine().trim().split(" ");
  54.             int f=Integer.parseInt(s[0]);
  55.             int t=Integer.parseInt(s[1]);
  56.             list[f].add(t);
  57.             tlist[t].add(f);
  58.         }
  59.  
  60.         for (int i=1;i<=v;i++)
  61.         {
  62.             DFS1(i);
  63.         }
  64.  
  65.         visited=new boolean[v+1];
  66.         while(!ts.isEmpty())
  67.         {
  68.             int node=ts.pop();
  69.             if(!visited[node])
  70.             {
  71.                 gno+=1;
  72.                 DFS2(node);
  73.             }
  74.         }
  75.         int outdeg[]=new int[gno+1];
  76.         for(int i=1;i<=v;i++)
  77.         {
  78.             for (int j=0;j<list[i].size();j++)
  79.             {
  80.                 if(comp[i]!=comp[list[i].get(j)])
  81.                 {
  82.                     outdeg[comp[i]]+=1;
  83.                 }
  84.             }
  85.         }
  86.  
  87.         long count=0;
  88.  
  89.         String sb ="";
  90.         for (int i = 1; i <= v; i++) {
  91.             if (outdeg[comp[i]] == 0) {
  92.                 count += 1;
  93.                 sb+=i+" ";
  94.             }
  95.         }
  96.  
  97.         bw.write(count + "\n");
  98.         bw.write(sb.trim() + "");
  99.         bw.close();
  100.     }
  101. }
  102.  
Success #stdin #stdout 0.11s 320576KB
comments ()
stdin
copy 
4 4
1 2
2 1
3 2
4 3
stdout
copy 
2
1 2
https://ideone.com/cvwbPT
problem CAPCITY, based on SPOJ submission 16829957 (JAVA), 2016-04-27 21:51:51
language:
Java (HotSpot 12)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!