day 9
2025-02-06 14:38:14
发布于：上海
32阅读
0回复
0点赞
pipipi无向图找环3
#include<bits/stdc++.h>
using namespace std;
int n,m;
char g[55][55];
bool vis[55][55];
int dir[4][2] = {{1,0},{-1,0},{0,-1},{0,1}};
bool ans;
void dfs(int x,int y,int fx,int fy){
if(ans)return;
vis[x][y] = 1;
for(int i=0;i<4;i++){
if(ans)return;
int nx = dir[i][0]+x;
int ny = dir[i][1]+y;
if(nx<1 || ny<1 || nx>n || ny>m || g[x][y]!=g[nx][ny])continue;
if(nx==fx && ny==fy)continue;
if(vis[nx][ny]==1){
ans=true;
return;
}else dfs(nx,ny,x,y);
}
}
int main(){
int T;
cin>>T;
while(T--){
ans = false;
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>g[i][j];
vis[i][j] = 0;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(vis[i][j]==0){
dfs(i,j,-1,-1);
}
}
}
if(ans)cout<<"YES";
else cout<<"NO";
cout<<endl;
}
return 0;
}
无向图找环1
#include<bits/stdc++.h>
using namespace std;
vector<int> a[100100];
vector<int> st;
bool vis[100100];//当前点有没有被搜过
int pos[100100];//当前点在栈里的位置；
int n,m,k;
void dfs(int x,int fa){
vis[x] = true;
st.push_back(x);
pos[x] = st.size();
for(int u:a[x]){
if(u == fa) continue;
if(!vis[u]) dfs(u,x);
else{
int len = pos[x]-pos[u]+1;
if(len>=k+1){
cout<<len<<endl;
for(int i = pos[u]-1;i<=pos[x]-1;i++){
cout<<st[i]<<" ";
}
exit(0);
}
}
}
st.pop_back();
}
int main(){
cin>>n>>m>>k;
for(int i = 1;i<=m;i++){
int x,y;
cin>>x>>y;
a[x].push_back(y);
a[y].push_back(x);
}
dfs(1,-1);
return 0;
}
pipipi无向图找环3 拓扑排序做法
#include<bits/stdc++.h>
using namespace std;
int n,m;
struct node{
int x,y;
};
char g[55][55];
int dg[55][55];
bool vis[55][55];
int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
int main(){
int T;
cin>>T;
while(T--){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>g[i][j];
dg[i][j] = 0;
vis[i][j]=false;
}
}
//搞度数
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
for(int k=0;k<4;k++){
int ni = i+dir[k][0];
int nj = j+dir[k][1];
if(ni<1 || nj<1 || ni>n || nj>m || g[i][j]!=g[ni][nj])continue;
dg[i][j]++;
dg[ni][nj]++;
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
dg[i][j]/=2;
}
}
queue<node> q;
int tot = n*m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(dg[i][j]<=1){
q.push({i,j});
}
}
}
while(q.size()){
node u = q.front();
int i = u.x,j = u.y;
q.pop();
tot--;
for(int k=0;k<4;k++){
int ni = i+dir[k][0];
int nj = j+dir[k][1];
if(ni<1 || nj<1 || ni>n || nj>m || g[i][j]!=g[ni][nj])continue;
if(--dg[ni][nj]==1)q.push({ni,nj});
}
}
if(tot==0)cout<<"NO";
else cout<<"YES";
cout<<endl;
}
return 0;
}
pipipi 有向图找环 2
有向图找到并输出环的模板，也基本都是这么写*
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5+10;
vector<int> ed[N];
vector<int> ans;
int pos[N], n, m, k;
int st[N], flag;
void dfs(int u)
{
if(flag) return ;
st[u] = 1;
ans.push_back(u);
pos[u] = ans.size() - 1;
for(int j : ed[u]) {
if(flag) return ;
if(st[j] == 1) {
cout << "YES\n";
cout << pos[u] - pos[j] + 1 << "\n";
for(int i = pos[j]; i <= pos[u]; i ++) {
cout << ans[i] << " ";
}
cout << "\n";
flag = 1;
return ;
}
if(st[j] == 0) {
dfs(j);
}
}
st[u] = 2;
ans.pop_back();
}
void solve()
{
cin >> n >> m;
flag = 0;
ans.clear();
for(int i = 1; i <= n; i ++) {
ed[i].clear();
st[i] = 0;
}
while(m --) {
int a, b;
cin >> a >> b;
ed[a].push_back(b);
}
for(int i = 1; i <= n; i ++) {
if(st[i]) continue;
dfs(i);
if(flag) return ;
}
cout << "NO\n";
}
int main(){
int T;
cin >> T;
while(T --) {
solve();
}
return 0;
}
pipipi 无向图找环 4
#include<bits/stdc++.h>
#include <assert.h>
using namespace std;
const int N = 2e3 + 5; // 最大结点数
typedef pair<int, int> pir; // 用于存储边的两个端点
std::vector<int> g[N]; // 邻接表表示图
std::vector<int> ring; // 存储当前找到的环
std::vector<int> st; // 存储深度优先搜索栈中的结点
int fa[N], vis[N], used[N], pos[N], n, m; // fa用于记录父节点，vis表示是否访问过，used表示是否使用过，pos记录节点在栈中的位置
// 深度优先搜索用于找到一个环
void dfs(int u, int f, int start) {
if (ring.size() > 0) return; // 如果已经找到一个环，直接返回
st.push_back(u); // 当前节点加入栈中
pos[u] = st.size(); // 记录当前节点在栈中的位置
vis[u] = 1; // 标记当前节点已访问
// 遍历所有邻接的节点
for (int v : g[u]) {
if (v == f) continue; // 如果是父节点，跳过
if (ring.size() > 0) return; // 如果已经找到环，直接返回
if (v == start) {
// 如果当前节点回到了起点，说明找到了一个环
for (int i = pos[v] - 1; i <= pos[u] - 1; i++) {
ring.push_back(st[i]); // 将环中的节点加入到ring中
}
}
else if (!vis[v]) {
// 如果当前节点v未访问，继续深度优先搜索
dfs(v, u, start);
}
}
if (ring.size() > 0) return; // 如果找到了环，直接返回
st.pop_back(); // 如果没有找到环，回溯
}
// 主解决函数
void solve() {
cin >> n >> m; // 输入节点数和边数
for (int i = 1; i <= n; i++) g[i].clear(); // 清空图的邻接表
// 输入图的边
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
// 遍历每个节点，尝试从该节点开始找一个环
for (int i = 1; i <= n; i++) {
if (g[i].size() < 4) continue; // 如果当前节点度数小于4，跳过
std::vector<int> have(n + 1); // 记录当前节点的邻接节点
{
for (int j : g[i]) have[j] = 1; // 标记i的邻接节点
ring.clear(); // 清空环
st.clear(); // 清空栈
for (int k = 1; k <= n; k++) vis[k] = 0; // 标记所有节点为未访问
}
// 使用深度优先搜索找一个环
dfs(i, i, i);
// 如果没有找到环，继续检查下一个节点
if (ring.size() < 2) continue;
for (int i = 1; i <= n; i++) used[i] = 0; // 清空used数组
// 处理环，缩短环的长度
int sz = ring.size();
for (int i = 2; i < ring.size(); i++) {
if (have[ring[i]]) {
sz = i + 1;
break;
}
}
// 截取合适大小的环
while (ring.size() > sz) {
ring.pop_back();
}
// 标记环上的节点
for (int v : ring) {
used[v] = 1;
}
// 寻找不在环上的两个点
int cnt = 0;
std::vector<pir> ans;
for (int v : g[i]) {
if (used[v] == 0 && cnt < 2) { // 如果v不在环上，且已经找到了两个点
cnt++;
ans.push_back({i, v}); // 记录这两个点和i的边
}
}
// 将环的边加入答案
for (int v = 0; v < sz; v++) {
ans.push_back({ring[v], ring[(v + 1) % sz]}); // 环上的边
}
// 输出结果
cout << "YES\n";
cout << ans.size() << '\n'; // 输出边数
for (auto [u, v] : ans) cout << u << " " << v << '\n'; // 输出每条边
return; // 找到一个满足条件的子图，直接返回
}
// 如果没有找到符合条件的子图，输出NO
cout << "NO\n";
}
int main() {
int t;
cin >> t; // 输入测试用例数量
while (t--) {
solve(); // 解决每个测试用例
}
}
无垠的环
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pir; // 定义一个 pair 类型，用于存储边 (u, v)
const int N = 5005; // 定义节点数的最大值，假设不超过 5000
std::vector<int> g[N]; // 图 g 用邻接表表示，g[i] 存储从节点 i 出发的边
pir edge[N]; // 存储每条边的起点和终点
int in[N]; // in[i] 记录节点 i 的入度（即有多少条边指向节点 i）
void solve() {
int n, m; // n 为节点数，m 为边数
cin >> n >> m; // 输入节点数和边数
// 输入每条边，并构建图和计算每个节点的入度
for (int i = 1; i <= m; i++) {
int u, v; // u, v 表示一条边从 u 指向 v
cin >> u >> v;
g[u].push_back(v); // 在图中添加从 u 到 v 的边
in[v]++; // 增加节点 v 的入度
edge[i] = {u, v}; // 保存边的信息
}
// 队列用于存储入度为 0 的节点（这些节点没有被其他节点指向）
queue<int> q;
// 将所有入度为 0 的节点加入队列
for (int i = 1; i <= n; i++) {
if (in[i] == 0) {
q.push(i); // 如果节点 i 的入度为 0，将其加入队列
}
}
int sz = 0; // sz 用于记录拓扑排序的节点数
// 拓扑排序过程
while (!q.empty()) {
int u = q.front(); // 取出队列中的一个节点
q.pop(); // 弹出队列
sz++; // 记录已处理的节点数
for (int v : g[u]) {
if (--in[v] == 0) { // 对每个邻接节点 v，减少其入度
q.push(v); // 如果 v 的入度变为 0，将 v 加入队列
}
}
}
// 如果拓扑排序中的节点数等于总节点数，说明图中没有环
if (sz == n) {
cout << 1 << '\n'; // 如果没有环，输出颜色数为 1
// 对每条边都输出颜色 2（随便设置一个颜色）
for (int i = 1; i <= m; i++) cout << 1 << " ";
} else {
cout << 2 << '\n'; // 如果有环，输出颜色数为 2
// 对每条边按照其起点和终点的关系选择颜色
for (int i = 1; i <= m; i++) {
auto [u, v] = edge[i]; // 获取边的起点 u 和终点 v
if (u < v) cout << 1 << " "; // 如果 u < v，给该边着色为 1
else cout << 2 << " "; // 否则给该边着色为 2
}
}
}
int main() {
solve();
}
这里空空如也
有帮助，赞一个