一、拓扑排序
1、hdu 1285 确定比赛名次
代码；（领接矩阵 避免 重复）
#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
#define MAXN 550
using namespace std;
int nVertex, nEdge;
int edge[MAXN][MAXN];
int inDeg[MAXN];
void topOrder(){
priority_queue<int, vector<int>, greater<int> >que;
for(int i = 1; i <= nVertex; i++){
if(inDeg[i] == 0)
que.push(i);
}
int flag = 0;
while(!que.empty()){
int front = que.top();
que.pop();
if(flag) printf(" ");
printf("%d", front);
flag = 1;
for(int i = 1; i <= nVertex; i++){
if(edge[front][i] == 0)
continue;
inDeg[i] -= edge[front][i];
if(inDeg[i] == 0)
que.push(i);
}
}
}
int main(){
while(scanf("%d %d", &nVertex, &nEdge) != EOF){
memset(edge, 0, sizeof(edge));
memset(inDeg, 0, sizeof(inDeg));
for(int i = 0; i < nEdge; i++){
int a, b;
scanf("%d %d", &a, &b);
//重复边多加了 入度 后面会一起 减掉
edge[a][b]++;
inDeg[b]++;
}
topOrder();
printf("\n");
}
return 0;
}
2、poj 1270 （dfs拓扑排序 输出所有情况 按照字典序大小）
代码：
#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
#include <iostream>
#define MAXN 550
using namespace std;
/*
a b c
a b c b
*/
int nVertex, nEdge;
int len;
char str[MAXN];
char str2[MAXN];
int nums[MAXN]; //所有字母
vector<int > edges[MAXN];
int degree[MAXN];
bool vis [MAXN];
vector<int > v;
void Init(){
v.clear();
memset(edges,0,sizeof(edges));
memset(degree,0,sizeof(degree));
}
void dfs(int cnt){
if(cnt > len) return;
if(cnt == len){
for(int i =0;i<len ;i++){
cout << char(v[i]+'a'-1) <<' ';
}
cout << endl;
return;
}
for(int i =0;i<len;i++){
if(!vis[nums[i]] && !degree[nums[i]]){
vis[nums[i]] = true;
for(int j =0;j<edges[nums[i]].size();j++){
degree[edges[nums[i]][j]]--;
}
v.push_back(nums[i]);
dfs(cnt + 1);
v.pop_back();
for(int j =0;j<edges[nums[i]].size();j++){
degree[edges[nums[i]][j]]++;
}
vis[nums[i]] = false;
}
}
}
int main(){
while(gets(str) != NULL){
Init();
int cnt = 0;
for(int i =0;i<strlen(str);i++){
if(str[i] <= 'z' && str[i] >= 'a'){
nums[cnt++] = str[i] - 'a' +1;
}
}
len = cnt;
gets(str2);
cnt = 0;
int pre =0;
for(int i =0;i<strlen(str2);i++){
if(str2[i] <= 'z' && str2[i] >= 'a'){
int now = str2[i] - 'a' +1;
//录入边关系 加度
if(cnt == 1) {
edges[pre].push_back(now);
cnt = 0;
degree[now]++;
continue;
}
if(cnt == 0){
pre = now; //前一点下标
cnt++;
}
}
}
dfs(0);
}
return 0;
}
3、hdu 3342 Legal or Not（简单 判断有向图 有无环路）
代码：
#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAXN 550
using namespace std;
/*
3 2
0 1
1 2
2 2
0 1
1 0
0 0
*/
int degree[MAXN];
vector<int > edges[MAXN];
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
void Init(int n){
memset(edges,0,sizeof(edges));
memset(degree,0,sizeof(degree));
}
int main(){
int n,m;
while(1){
n = read();
m = read();
if(n == 0 && m == 0) break;
Init(n);
for(int i =1;i<=m;i++){
int a,b;
a = read();
b = read();
//避免 重复边
if(find(edges[a].begin(),edges[a].end(),b) == edges[a].end()){
edges[a].push_back(b); //输入边关系
degree[b]++; //入度加一
}
}
queue<int> q;
for(int i = 0;i<n;i++){
if(degree[i] == 0) q.push(i);
}
int cnt = 0;
while(!q.empty()){
int u = q.front();
q.pop();
cnt++;
for(int i = 0;i<edges[u].size();i++){
int v = edges[u][i];
if(--degree[v] == 0) q.push(v);
}
}
if(cnt == n) cout <<"YES"<<endl;
else cout << "NO" << endl;
}
return 0;
}
4、hdu2647 Reward （带权值得 反向建图）
代码：
#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAXN 10005
using namespace std;
/*
3 2
0 1
1 2
2 2
0 1
1 0
0 0
*/
int w[MAXN];
int degree[MAXN];
vector<int > edges[MAXN];
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
void Init(int n){
memset(w,0,sizeof(w));
memset(edges,0,sizeof(edges));
memset(degree,0,sizeof(degree));
}
int main(){
int n,m;
while(scanf("%d %d",&n,&m) != EOF){
Init(n);
for(int i =1;i<=m;i++){
int a,b;
//反向建图 便于 等下 从最底层 开始 bfs
b = read();
a = read();
//避免 重复边
if(find(edges[a].begin(),edges[a].end(),b) == edges[a].end()){
edges[a].push_back(b); //输入边关系
degree[b]++; //入度加一
}
}
queue<int> q;
for(int i = 1;i<=n;i++){
if(degree[i] == 0) q.push(i);
}
int cnt = 0;
while(!q.empty()){
int u = q.front();
q.pop();
cnt++;
for(int i = 0;i<edges[u].size();i++){
int v = edges[u][i];
//画图推导这里 向上赋值
if(--degree[v] == 0) q.push(v),w[v] = w[u]+1;
}
}
long long sum =0;
if(cnt == n){
for(int i = 1;i<=n;i++) {
sum += w[i];
}
sum += 888*n;
cout << sum<< endl;
}
else cout << -1 << endl;
}
return 0;
}
网友评论