poj 4084:拓撲排序
poj 4084:拓撲排序
很好的題目，惡心的算法
描述
給出一個圖的結構，輸出其拓撲排序序列，要求在同等條件下，編號小的頂點在前。
輸入
若干行整數，第一行有2個數，分別為頂點數v和弧數a，接下來有a行，每一行有2個數，分別是該條弧所關聯的兩個頂點編號。
v<=100, a<=500
輸出
若干個空格隔開的頂點構成的序列(用小寫字母)。
樣例輸入
6 8
1 2
1 3
1 4
3 2
3 5
4 5
6 4
6 5
樣例輸出
v1 v3 v2 v6 v4 v5
解題方案
顯然這是有向圖，然後用了一個個人感覺惡心的算法，個人建了一個倒排表，例如針對上述數據
IDCjrMi7uvO+zc6qzdjGy8XF0PK94r72wcvX9sHLuty6w7XExsy15jwvcD4KPHA+PGJyPgo8L3A+CjxwPrj2yMu0+sLrPC9wPgo8cD48cHJlIGNsYXNzPQ=="brush:java;">#include
#include
#include
#include
#include
using namespace std;
typedef pair edge;
typedef list *elem;
void Topological_sort(vector &invertList);
void read_data(edge* & data,int &v,int &e);
void main_solution();
vector invert_list(edge * data,int v,int e);
int main()
{
main_solution();
system("pause");
return 0;
}
void read_data(edge* & data,int &v,int &e)
{
ifstream reader;
reader.open("data.txt");
reader>>v;
reader>>e;
data = new edge[e];
for(int i=0;i>data[i].first;
reader>>data[i].second;
}
reader.close();
}
void main_solution()
{
edge* data;
int v;
int e;
read_data( data,v,e );
vector invertList = invert_list( data,v,e );
Topological_sort(invertList);
}
vector invert_list(edge * data,int v,int e)
{
vector result;
result.resize(v);
for(int i =0;i;
}
for(int i=0;ipush_back(data[i].first);
}
return result ;
}
void Topological_sort(vector &invertList)
{
const int v = invertList.size();
bool * flag = new bool[v];
for(int i=0;iempty() )
{
break;
}
}
// 踢出 Vj+1
flag[j] = false ;
for( int n=0;n::iterator it = invertList[n]->begin(); it != invertList[n]->end(); it++)
{
if( *it == j+1 )
{
invertList[n]->erase(it);
break;
}
}
}
cout<<"v"<
