有向图的拓扑排序
#include
#include
#include
using namespace std;
const int N =100010;
int n ,m;
int h[N],e[N],ne[N],idx;
int q[N],d[N];
void add(int a ,int b)
{
e[idx]=b ,ne[idx]=h[a],h[a]=idx ++;
}
bool topsort()
{
int hh=0,tt=-1;
for(int i=1;i<=n;i++)
if(!d[i]) //搜索所有入度为0的点
q[++tt]=i;
while(hh<=tt)
{
int t = q[hh++];
for (int i =h[t];i!=-1;i=ne[i])
{
int j =e[i];
d[j] --;
if (d[j] ==0) q[++ tt] = j; //减到0加入队尾
}
}
return tt = n-1; //能撑到最后说明符合条件
}
int main()
{
cin >> n >> m;
memset(h,-1,sizeof h );
for (int i = 0;i {
int a ,b;
cin >> a >> b;
add(a,b);
d[b]++; //入度加1
}
if (topsort())
{
for (int i =0;i puts("");
}
else puts("-1");
return 0;
}
#include
#include
#include
using namespace std;
const int N =100010;
int n ,m;
int h[N],e[N],ne[N],idx;
int q[N],d[N];
void add(int a ,int b)
{
e[idx]=b ,ne[idx]=h[a],h[a]=idx ++;
}
bool topsort()
{
int hh=0,tt=-1;
for(int i=1;i<=n;i++)
if(!d[i]) //搜索所有入度为0的点
q[++tt]=i;
while(hh<=tt)
{
int t = q[hh++];
for (int i =h[t];i!=-1;i=ne[i])
{
int j =e[i];
d[j] --;
if (d[j] ==0) q[++ tt] = j; //减到0加入队尾
}
}
return tt = n-1; //能撑到最后说明符合条件
}
int main()
{
cin >> n >> m;
memset(h,-1,sizeof h );
for (int i = 0;i
int a ,b;
cin >> a >> b;
add(a,b);
d[b]++; //入度加1
}
if (topsort())
{
for (int i =0;i
}
else puts("-1");
return 0;
}
八皇后 （dfs）
#include
using namespace std;
const int N =20;
int n;
char g[N][N];
bool col[N],dg[N],udg[N]; //判断直边，两个斜边是否被占用
void dfs(int u)
{
if(u==n)//到最后一行
{
for (int i=0;i puts("");
return;
}
for(int i =0;i if(!col[i] && !dg[u+i] && !udg[n-u+i]) //类似于截距
{
g[u][i]='Q';
col[i]=dg[u+i]=udg[n-u+i]=true;
dfs(u+1);
col[i] = dg[u+i] = udg[n-u+i]=false;
g[u][i]='.';
}
}
int main()
{
cin >> n;
for (int i =0;i for (int j=0;jg[i][j]='.';
dfs(0);
return 0;
}
#include
using namespace std;
const int N =20;
int n;
char g[N][N];
bool col[N],dg[N],udg[N]; //判断直边，两个斜边是否被占用
void dfs(int u)
{
if(u==n)//到最后一行
{
for (int i=0;i
return;
}
for(int i =0;i
{
g[u][i]='Q';
col[i]=dg[u+i]=udg[n-u+i]=true;
dfs(u+1);
col[i] = dg[u+i] = udg[n-u+i]=false;
g[u][i]='.';
}
}
int main()
{
cin >> n;
for (int i =0;i
dfs(0);
return 0;
}
DFS模板
#include
using namespace std;
const int N =10;
int n;
int path[N];
bool st[N]; //判断是否被使用过
void dfs(int u)
{
if(u==n)//遍历到最后一层就直接返回
{
for(int i =0;i puts("");
return;
}
for(int i =1;i<=n;i++)
if(!st[i])
{
path[u]=i;
st[i]=true;
dfs(u+1);
st[i]=false; //恢复现场
}
}
int main()
{
cin >> n;
dfs(0);
return 0;
}
#include
using namespace std;
const int N =10;
int n;
int path[N];
bool st[N]; //判断是否被使用过
void dfs(int u)
{
if(u==n)//遍历到最后一层就直接返回
{
for(int i =0;i
return;
}
for(int i =1;i<=n;i++)
if(!st[i])
{
path[u]=i;
st[i]=true;
dfs(u+1);
st[i]=false; //恢复现场
}
}
int main()
{
cin >> n;
dfs(0);
return 0;
}
✋热门推荐