tj

tarjan.cpp

#include <cstdio>
#include <climits>
using namespace std;

const int POOL_SIZE = 10000000;
const int QUEUE_SIZE = 10000000;
const int NODES_SIZE = 10000000;

struct edge_node {
	int dest;
	edge_node *next;
};

edge_node pool[POOL_SIZE];
int pool_top;

inline void pool_reset() {
	for(int i = 0; i <= pool_top; ++i) {
		(pool + i)->next = 0;
	}
}

struct fast_vector {
	edge_node *ptr;
	struct iter {
		edge_node *current;
		inline edge_node * get() {
			return current;
		}
		
		inline int dest() {
			return current->dest;
		}
		
		inline void inc() {
			current = current->next;
		}
		
		inline bool is_last() {
			return current == 0;
		}
		
		inline iter(edge_node *e) {
			current = e;
		}
	};
	
	inline void add(int dest) {
		edge_node *e = pool + (++ pool_top);
		e->next = ptr;
		e->dest = dest;
		ptr = e;
	}
	
	inline iter begin() {
		return iter(ptr);
	}
	
	inline void clear() {
		ptr = 0;
	}
	
	fast_vector() {
		ptr = 0;
	}
};

struct fast_stack {
	int array[NODES_SIZE];
	bool in_stack[NODES_SIZE];
	int top;
	
	int pop() {
		int x = array[top];
		top --;
		in_stack[x] = false;
		return x;
	}
	
	void push(int x) {
		array[++ top] = x;
		in_stack[x] = true;
	}
	
	bool has(int x) {
		return in_stack[x];
	}
	
	fast_stack() {
		top = 0;
	}
};

inline void add_edge(fast_vector *fv, int u, int v) {
	fv[u].add(v);
}

int N;

fast_vector edges[NODES_SIZE];

int Index, DFN[NODES_SIZE], Low[NODES_SIZE], P[NODES_SIZE];

int scc_top;

bool Visited[NODES_SIZE];

fast_stack Stack;

void jan(int u) {
	Visited[u] = true;
	DFN[u] = Low[u] = ++ Index;
	Stack.push(u);
	for(fast_vector::iter it = edges[u].begin(); ! it.is_last(); it.inc()) {
		int v = it.dest();
		if(! Visited[v]) {
			jan(v);
			if(Low[u] > Low[v]) Low[u] = Low[v]; 
		} else if (Stack.has(v)) {
			if(Low[u] > DFN[v]) Low[u] = DFN[v];
		}
	}
	if(DFN[u] == Low[u]) {
		++ scc_top;
		int v;
		do {
			v = Stack.pop();
			P[v] = scc_top;
		} while(u != v);
	}
}

void tar(int u) {
	Index = 1;
	jan(u);
}

void print_graph() {
	for(int i = 1; i <= N; ++i)
		for(fast_vector::iter it = edges[i].begin(); ! it.is_last(); it.inc())
			printf("%d -> %d\n", i, it.dest());
}

int main() {
	int M;
	scanf("%d%d", &N, &M);
	while(M --) {
		int u, v;
		scanf("%d%d", &u, &v);
		add_edge(edges, u, v);
	}
	print_graph();
	
	tar(1);
	for(int i = 1; i <= N; ++ i) {
		printf("%d ", P[i]);
	}
	return 0;
}