Archive for the ‘Topological sort’ Category

UVA – 1243 – Polynomial-time Reductions   Leave a comment


First we compress the SCC and count the relations needed by each SCC add them to total, then using the graph’s transitive closure we eliminate the extra edges however we need to eliminate them in topological order of nodes.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class PolynomialTimeReduction {
	public static int find(int i, int[] p) {
		return p[i] = (p[i] == i) ? i : find(p[i], p);
	}

	public static void topsort(int i, boolean[] v, byte[][] g,
			Stack<Integer> sort) {
		if (!v[i]) {
			v[i] = true;
			for (int j = 0; j < g.length; j++)
				if (g[i][j] != 0)
					topsort(j, v, g, sort);
			sort.push(i);
		}
	}

	public static void main(String[] args) throws Exception {
		InputReader in = new InputReader(System.in);
		int cc = 1;
		while (true) {
			int n = in.nextInt();
			int m = in.nextInt();
			if (n == 0 && m == 0)
				return;
			byte[][] g = new byte[n][n];
			for (int i = 0; i < m; i++)
				g[in.nextInt() - 1][in.nextInt() - 1] = 1;
			for (int k = 0; k < n; k++)
				for (int i = 0; i < n; i++)
					for (int j = 0; j < n; j++)
						g[i][j] |= g[i][k] & g[k][j];
			int[] p = new int[n];
			for (int i = 0; i < n; i++)
				p[i] = i;
			int c = n;
			for (int i = 0; i < g.length; i++)
				for (int j = 0; j < g.length; j++)
					if (g[i][j] == 1 && g[j][i] == 1
							&& find(i, p) != find(j, p)) {
						p[find(i, p)] = find(j, p);
						c--;
					}
			int[] count = new int[n];
			byte[][] g2 = new byte[c][c];
			int top = 0;
			int tot = 0;
			for (int i = 0; i < n; i++)
				count[p[i]]++;
			for (int i = 0; i < n; i++)
				if (count[i] > 1)
					tot += count[i];
			for (int i = 0; i < count.length; i++) {
				if (count[i] != 0)
					count[i] = top++;// map back
			}
			for (int i = 0; i < g.length; i++) {
				for (int j = 0; j < g.length; j++) {
					g2[count[p[i]]][count[p[j]]] = g[i][j];
				}
			}
			for (int i = 0; i < g2.length; i++)
				g2[i][i] = 0;
			boolean[] v = new boolean[c];
			Stack<Integer> toposort = new Stack<Integer>();
			for (int i = 0; i < c; i++)
				topsort(i, v, g2, toposort);
			while (!toposort.isEmpty()) {
				int current = toposort.pop();
				for (int j = 0; j < c; j++) {
					if (g2[current][j] == 1) {
						for (int k = 0; k < c; k++) {
							g2[current][k] ^= g2[j][k] & g2[current][k];
						}
					}
				}
				for (int i = 0; i < g2.length; i++)
					tot += g2[current][i];
			}
			System.out.printf("Case %d: %d\n", cc++, tot);
		}
	}

	static class InputReader {
		private BufferedReader reader;
		private StringTokenizer tokenizer;

		public InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream));
			tokenizer = null;
		}

		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());
		}
	}
}

Advertisements

Posted June 24, 2012 by epicrado in Floyd warshall, Topological sort

UVA – 124 – Following Orders   Leave a comment


import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;

public class FollowingOrders {
	static LinkedList<Integer>[] G;
	static int[] indegree;
	static int[] map = new int[128];
	static char[] unmap;
	static int n;
	static StringBuilder out;
	static char[] res;

	public static void dfs(int left) {
		if (left == 0)
			out.append(new String(res) + '\n');
		for (int i = 0; i < n; i++) {
			if (indegree[i] == 0) {
				indegree[i] = -1;
				res[n - left] = unmap[i];
				for (int j : G[i])
					indegree[j]--;
				dfs(left - 1);
				for (int j : G[i])
					indegree[j]++;
				indegree[i] = 0;
			}
		}
	}

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		boolean flag = false;
		while (in.hasNext()) {
			if (flag)
				System.out.println();
			flag = true;
			String[] symb = in.nextLine().split(" ");
			String[] comp = in.nextLine().split(" ");
			Arrays.sort(symb);
			out = new StringBuilder();
			n = symb.length;
			unmap = new char[n];
			G = new LinkedList[symb.length];
			indegree = new int[symb.length];
			for (int i = 0; i < G.length; i++)
				G[i] = new LinkedList<Integer>();
			for (int i = 0; i < symb.length; i++) {
				map[symb[i].charAt(0)] = i;
				unmap[i] = symb[i].charAt(0);
			}
			res = new char[n];
			for (int i = 0; i < comp.length; i += 2) {
				int s = map[comp[i].charAt(0)];
				int t = map[comp[i + 1].charAt(0)];
				indegree[t]++;
				G[s].add(t);
			}
			dfs(n);
			System.out.print(out);
		}
	}
}

Posted January 25, 2012 by epicrado in Topological sort

UVA – 872 – Ordering   Leave a comment


#include <stdio.h>
char G[26][26];
char mark[26];
int in[26];
char out[100];
char cache[100];
int count;
void dfs(int ind,int all)
{
	if(ind==all)
	{
		int i;
		putchar(out[0]);
		for(i=1;out[i];i++)
		{
			putchar(' ');
			putchar(out[i]);
		}
		putchar('\n');
		count++;
	}
	else
	{
		int i,j;
		for(i=0;i<26;i++)
			if(mark[i]&&!in[i])
			{
				mark[i]=0;
				for(j=0;j<26;j++)
					if(mark[j]&&G[i][j])
						in[j]--;
				out[ind]=i+'A';
				dfs(ind+1,all);
				mark[i]=1;
				for(j=0;j<26;j++)
					if(mark[j]&&G[i][j])
						in[j]++;
			}
	}
}
int main()
{
	int i,n,j,len;
	scanf("%d",&n);
	char buffer[1000];
	getchar();
	while(n--)
	{
		len = 0;
		for(i=0;i<26;i++)
		{
			for(j=0;j<26;j++)
				G[i][j]=0;
			in[i]=mark[i]=0;
		}
		getchar();
		gets(buffer);
		for(i=0;buffer[i];i++)
			if(buffer[i]!=' '&&!mark[buffer[i]-'A'])
			{
				mark[buffer[i]-'A']=1;
				len++;
			}
		gets(buffer);
		for(i=0;buffer[i];i++)
			if(buffer[i]!=' ')
				if(!G[buffer[i]-'A'][buffer[i+2]-'A'])
				{
					in[buffer[i+2]-'A']++;
					G[buffer[i]-'A'][buffer[i+2]-'A']=1;
					i+=2;
				}
		count = 0;
		dfs(0,len);
		if(!count)
			puts("NO");
		if(n)
			putchar('\n');
	}
	return 0;
}

Posted September 7, 2011 by epicrado in Topological sort

UVA – 200 – Rare Order   2 comments


#include <string>
#include <iostream>
#include <vector>
#include <queue>
#include <stdio.h>
bool G[26][26];
int in[26];
bool mark[26];
using namespace std;
int main()
{
	string v[10000];
	int i=0;
	while(cin>>v[i])
	{
		if(v[i][0]=='#')
		{
			for(int j=0;j<26;j++)
			{
				for(int k = 0;k<26;k++)
					G[j][k]=0;
				in[j]=0;
				mark[j]=false;
			}
			for(int j = 0;j<i;j++)
				for(int k = j+1;k<i;k++)
				{
					unsigned int c = 0;
					while(c<v[j].length()&&c<v[k].length()&&v[j][c]==v[k][c])c++;
					if(c<v[j].length()&&c<v[k].length()&&!G[v[j][c]-'A'][v[k][c]-'A'])
					{
						mark[v[j][c]-'A']=mark[v[k][c]-'A']=true;
						in[v[k][c]-'A']++;
						G[v[j][c]-'A'][v[k][c]-'A']=true;
					}
				}
			bool done = false;
			while(!done)
			{
				done = true;
				for(int j = 0;j<26;j++)
					if(mark[j]&&!in[j])
					{
						done = false;
						for(int k = 0;k<26;k++)
							if(G[j][k])
								in[k]--;
						mark[j]=0;
						putchar(j+'A');
					}

			}
			putchar('\n');
			i = 0;
		}
		else
			i++;
	}
	return 0;
}

Posted September 7, 2011 by epicrado in Topological sort

UVA – 11060 – Beverages   Leave a comment


#include <stdio.h>
#include <stdlib.h>
#include <queue>
#include <map>
#include <string>
#include <iostream>
using namespace std;
int main()
{
	int n;
	int cc=1;
	while(cin>>n)
	{
		bool G[n][n];
		bool mark[n];
		int in[n];
		for(int i =0;i<n;i++)
		{
			in[i]=mark[i]=0;
			for(int j = 0;j<n;j++)
				G[i][j]=0;
		}
		map<string,int> ind;
		string word[n];
		for(int i = 0;i<n;i++)
		{
			string s;
			cin>>s;
			ind[s]=i;
			word[i]=s;
		}
		int m;
		cin>>m;
		for(int i = 0;i<m;i++)
		{
			string s1,s2;
			cin>>s1>>s2;
			if(!G[ind[s1]][ind[s2]])
			{
				G[ind[s1]][ind[s2]]=true;
				in[ind[s2]]++;
			}
		}
		printf("Case #%d: Dilbert should drink beverages in this order:",cc++);
		bool done = false;
		while(!done)
		{
			done = true;
			for(int i  = 0;i<n;i++)
			if(!mark[i]&&in[i]==0)
			{
				done=0;
				mark[i]=1;
				cout<<" "<<word[i];
				for(int j =0;j<n;j++)
					if(G[i][j])
						in[j]--;
				i = -1;
			}
		}
		putchar('.');
		putchar('\n');
		putchar('\n');
	}
}

Posted September 7, 2011 by epicrado in Topological sort

UVA – 10305 – Ordering Tasks   Leave a comment


bounds are small so we could use this simple algorithm AC in 0.004

#include <stdio.h>
char matrix[200][200];
char in[200];
void fix(int,int,int);
void topological(int v)
{
	int i,fin;
	fin = 0;
	while(fin<v)
	{
		for(i=1;i<=v;i++)
			if(in[i]==0)
				fix(i,v,fin++);
	}
}
void fix(int i,int v,int current)
{
	int j;
	if(current)
		putchar(' ');
	printf("%d",i);
	in[i]=-1;
	for(j=1;j<=v;j++)
		if(matrix[i][j])
			in[j]--;
}
int main()
{
	int v,e,i,j,f,s;
	scanf("%d %d",&v,&e);
	while(v||e)
	{
		for(i=1;i<=v;i++)
			for(j=1;j<=v;j++)
				in[i] = matrix[i][j]=0;
		for(i=0;i<e;i++)
		{
			scanf("%d %d",&f,&s);
			matrix[f][s]=1;
			in[s]++;
		}
		topological(v);
		putchar('\n');
		scanf("%d %d",&v,&e);
	}
	return 0;
}

Posted August 16, 2011 by epicrado in Topological sort