Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.BufferedReader;
- import java.io.FileReader;
- import java.io.FileWriter;
- import java.io.IOException;
- import java.io.PrintWriter;
- import java.util.StringTokenizer;
- import java.util.ArrayList;
- public class eMain implements Runnable {
- StringTokenizer st;
- BufferedReader in;
- PrintWriter out;
- ArrayList<Integer>[] graph;
- ArrayList<Integer> answ;
- int n,m;
- int num;
- int time=0;
- int pr[];
- int counter=0;
- int anscol[];
- int aa[];
- int bb[];
- int enter[];
- int colors[];
- int leave[];
- int low[];
- int art[];
- int nums[];
- public static void main(String[] args) {
- new Thread(new eMain()).run();
- }
- public void run() {
- try {
- in = new BufferedReader(new FileReader("biconv.in"));
- out = new PrintWriter(new FileWriter("biconv.out"));
- solve();
- } catch (Exception e) {
- e.printStackTrace();
- } finally {
- out.flush();
- out.close();
- }
- }
- String nextToken() throws IOException {
- while (st == null || !st.hasMoreTokens()) {
- st = new StringTokenizer(in.readLine());
- }
- return st.nextToken();
- }
- int nextInt() throws NumberFormatException, IOException {
- return Integer.parseInt(nextToken());
- }
- long nextLong() throws NumberFormatException, IOException {
- return Long.parseLong(nextToken());
- }
- double nextDouble() throws NumberFormatException, IOException {
- return Double.parseDouble(nextToken());
- }
- int min (int a, int b) {
- if (a<=b) {
- return a;
- } else {
- return b;
- }
- }
- void DFSVISIT(int a) {
- int kids = 0;
- colors[a] = 1;
- low[a]=enter[a]=++time;
- int s=graph[a].size();
- for (int i=0; i<s; i++){
- int ii=aa[graph[a].get(i)];
- if(colors[ii]==0) {
- pr[ii]=a;
- DFSVISIT(ii);
- low[a]=min(low[a],low[ii]);
- if ((pr[a]!=-1)&&(low[ii]>=enter[a])) {
- art[a]=1;
- }
- kids++;
- } else if((colors[ii]== 1) && (ii!=pr[a])) {
- low[a] = min(low[a],enter[ii]);
- }
- }
- if (pr[a]==-1){
- if (kids>=2) {
- art[a]=1;
- } else {
- art[a]=0;
- }
- }
- colors[a]=2;
- leave[a]=++time;
- }
- void DFS() {
- for (int i=0; i<n; i++) {
- if (colors[i]==0){
- DFSVISIT(i);
- }
- }
- }
- void DFSVISIT2(int a,int b){
- colors[a]=1;
- int s=graph[a].size();
- for (int i=0; i<s; i++){
- int ii=aa[graph[a].get(i)];
- if (colors[ii]==1){
- anscol[graph[a].get(i)%m]=b;
- anscol[graph[a].get(i)]=b;
- }
- }
- for (int i=0; i<s; i++){
- int ii=aa[graph[a].get(i)];
- if (colors[ii]==0){
- if (art[ii]==1) {
- counter++;
- anscol[graph[a].get(i)%m]=counter;
- anscol[graph[a].get(i)]=counter;
- DFSVISIT2(ii,counter);
- } else {
- anscol[graph[a].get(i)%m]=b;
- anscol[graph[a].get(i)]=b;
- DFSVISIT2(ii,b);
- }
- }
- }
- colors[a]=2;
- }
- @SuppressWarnings("unchecked")
- void solve() throws NumberFormatException, IOException {
- n=nextInt();
- m=nextInt();
- answ = new ArrayList();
- colors=new int[n];
- pr=new int[n];
- low=new int[n];
- enter=new int[n];
- leave=new int[n];
- art=new int[n];
- nums=new int[n];
- anscol=new int[2*m];
- aa=new int[2*m];
- bb=new int[2*m];
- for (int i=0; i<n; i++) {
- pr[i]=-1;
- art[i]=0;
- }
- graph=new ArrayList[n];
- for(int i = 0; i < n; i++) {
- graph[i] = new ArrayList<Integer>();
- }
- for (int i=0; i<m; i++) {
- int a, b;
- a=nextInt();
- b=nextInt();
- graph[a-1].add(i);
- graph[b-1].add(i+m);
- aa[i]=b-1;
- aa[i+m]=a-1;
- }
- DFS();
- for (int i=0; i<n;i++) {
- colors[i]=0;
- }
- for (int i=0; i<n;i++) {
- counter++;
- if (colors[i]==0) {
- DFSVISIT2(i,1);
- }
- }
- for (int i=0; i<n; i++){
- if (art[i]==1) {
- out.print(i+1+" ");
- }
- }
- out.println("");
- out.println(counter);
- for (int i=0; i<m; i++){
- out.print(anscol[i]+" ");
- }
- }
- }
Add Comment
Please, Sign In to add comment