#include <bits/stdc++.h>
#define fin std::cin
#define fout std::cout
// std::ifstream fin("potemkin.in");
// std::ofstream fout("potemkin.out");
class Graph {
public:
std::vector <std::vector <int>> edge;
std::vector <std::vector <bool>> adj;
int V;
Graph() {};
Graph(int size) {
V = size;
edge.resize(V + 1);
adj.resize(V + 1);
for(int i = 0; i < adj.size(); i ++)
adj[i].resize(V + 1);
}
void clear() {
edge.clear();
adj.clear();
V = 0;
}
void addEdge(int src, int dest) {
edge[src].push_back(dest);
edge[dest].push_back(src);
adj[src][dest] = true;
adj[dest][src] = true;
}
};
bool foundSol = false;
bool* visited;
std::vector <int> sol;
void bfs(int root, int start, int end, std::unordered_set <int>& nodes, Graph& graph) {
std::deque <int> dq;
dq.push_back(start);
int dist[graph.V + 1] = {};
dist[start] = 1;
while(dq.empty() == false) {
int node = dq.front();
dq.pop_front();
for(int next: graph.edge[node]) {
if(next == root)
continue;
if(nodes.find(next) == nodes.end())
continue;
if(dist[next] == 0) {
dist[next] = dist[node] + 1;
dq.push_back(next);
}
}
}
while(end != start) {
fout << end << ' ';
for(int next: graph.edge[end])
if(dist[next] == dist[end] - 1) {
end = next;
break;
}
}
fout << start << ' ' << root << '\n';
}
void dfs(int& node, int& root, std::unordered_set <int>& nodes, std::unordered_set <int>& g, std::unordered_set <int>& ngh, Graph& graph) {
visited[node] = true;
g.insert(node);
for(int next: graph.edge[node]) {
if(nodes.find(next) == nodes.end())
continue;
if(visited[next] == false) {
if(graph.adj[root][next] == false) {
dfs(next, root, nodes, g, ngh, graph);
}
else {
if(ngh.find(next) != ngh.end())
continue;
for(auto i: ngh) {
if(graph.adj[i][next] == false) {
foundSol = true;
bfs(root, i, next, nodes, graph);
return;
}
}
ngh.insert(next);
}
}
#include <bits/stdc++.h>
// #define fin std::cin
// #define fout std::cout
std::ifstream fin("potemkin.in");
std::ofstream fout("potemkin.out");
class Graph {
public:
std::vector <std::vector <int>> edge;
std::vector <std::vector <bool>> adj;
int V;
Graph() {};
Graph(int size) {
V = size;
edge.resize(V + 1);
adj.resize(V + 1);
for(int i = 0; i < adj.size(); i ++)
adj[i].resize(V + 1);
}
void clear() {
edge.clear();
adj.clear();
V = 0;
}
void addEdge(int src, int dest) {
edge[src].push_back(dest);
edge[dest].push_back(src);
adj[src][dest] = true;
adj[dest][src] = true;
}
};
bool foundSol = false;
bool* visited;
std::vector <int> sol;
void bfs(int root, int start, int end, std::unordered_set <int>& nodes, Graph& graph) {
std::deque <int> dq;
dq.push_back(start);
int dist[graph.V + 1] = {};
dist[start] = 1;
while(dq.empty() == false) {
int node = dq.front();
dq.pop_front();
for(int next: graph.edge[node]) {
if(next == root)
continue;
if(nodes.find(next) == nodes.end())
continue;
if(dist[next] == 0) {
dist[next] = dist[node] + 1;
dq.push_back(next);
}
}
}
while(end != start) {
fout << end << ' ';
for(int next: graph.edge[end])
if(dist[next] == dist[end] - 1) {
end = next;
break;
}
}
fout << start << ' ' << root << '\n';
}
void dfs(int& node, int& root, std::unordered_set <int>& nodes, std::unordered_set <int>& g, std::unordered_set <int>& ngh, Graph& graph) {
visited[node] = true;
g.insert(node);
for(int next: graph.edge[node]) {
if(nodes.find(next) == nodes.end())
continue;
if(visited[next] == false) {
if(graph.adj[root][next] == false) {
dfs(next, root, nodes, g, ngh, graph);
}
else {
if(ngh.find(next) != ngh.end())
continue;
for(auto i: ngh) {
if(graph.adj[i][next] == false) {
foundSol = true;
bfs(root, i, next, nodes, graph);
return;
}
}
ngh.insert(next);
}
}
if(foundSol == true)
return;
}
}
Graph graph;
void solve(std::unordered_set <int>& nodes) {
int root = *nodes.begin(), V = graph.V;
for(auto node: nodes)
visited[node] = false;
int comp = 0;
std::vector <std::unordered_set <int>> nextNodes;
for(auto i: nodes) {
if(visited[i] == false and graph.adj[root][i] == false and i != root) {
std::unordered_set <int> g, ngh;
dfs(i, root, nodes, g, ngh, graph);
if(foundSol == true)
return;
nextNodes.push_back({});
for(auto j: g)
nextNodes[comp].insert(j);
for(auto j: ngh)
nextNodes[comp].insert(j);
comp ++;
}
}
nodes.clear();
for(int i = 0; i < nextNodes.size(); i ++)
solve(nextNodes[i]);
}
int main(){
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);
int V, E;
fin >> V >> E;
graph = Graph(V);
visited = new bool[V+1];
for(int i = 0, src, dest; i < E; i ++) {
fin >> src >> dest;
graph.addEdge(src, dest);
}
std::unordered_set <int> nodes;
for(int i = 1; i <= V; i ++)
nodes.insert(i);
solve(nodes);
if(foundSol == false)
fout << "no\n";
return 0;
}
if(foundSol == true)
return;
}
}
Graph graph;
void solve(std::unordered_set <int>& nodes) {
int root = *nodes.begin(), V = graph.V;
for(auto node: nodes)
visited[node] = false;
int comp = 0;
std::vector <std::unordered_set <int>> nextNodes;
for(auto i: nodes) {
if(visited[i] == false and graph.adj[root][i] == false and i != root) {
std::unordered_set <int> g, ngh;
dfs(i, root, nodes, g, ngh, graph);
if(foundSol == true)
return;
nextNodes.push_back({});
for(auto j: g)
nextNodes[comp].insert(j);
for(auto j: ngh)
nextNodes[comp].insert(j);
comp ++;
}
}
nodes.clear();
for(int i = 0; i < nextNodes.size(); i ++)
solve(nextNodes[i]);
}
int main(){
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);
int V, E;
fin >> V >> E;
graph = Graph(V);
visited = new bool[V+1];
for(int i = 0, src, dest; i < E; i ++) {
fin >> src >> dest;
graph.addEdge(src, dest);
}
std::unordered_set <int> nodes;
for(int i = 1; i <= V; i ++)
nodes.insert(i);
solve(nodes);
if(foundSol == false)
fout << "no\n";
return 0;
}
Compilation message
indcyc.cpp: In constructor 'Graph::Graph(int)':
indcyc.cpp:21:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
21 | for(int i = 0; i < adj.size(); i ++)
| ~~^~~~~~~~~~~~
indcyc.cpp: In function 'void dfs(int&, int&, std::unordered_set<int>&, std::unordered_set<int>&, std::unordered_set<int>&, Graph&)':
indcyc.cpp:110:18: error: qualified-id in declaration before '(' token
110 | std::ifstream fin("potemkin.in");
| ^
indcyc.cpp:111:19: error: qualified-id in declaration before '(' token
111 | std::ofstream fout("potemkin.out");
| ^
indcyc.cpp: In constructor 'dfs(int&, int&, std::unordered_set<int>&, std::unordered_set<int>&, std::unordered_set<int>&, Graph&)::Graph::Graph(int)':
indcyc.cpp:125:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
125 | for(int i = 0; i < adj.size(); i ++)
| ~~^~~~~~~~~~~~
indcyc.cpp: In function 'void dfs(int&, int&, std::unordered_set<int>&, std::unordered_set<int>&, std::unordered_set<int>&, Graph&)':
indcyc.cpp:149:87: error: a function-definition is not allowed here before '{' token
149 | void bfs(int root, int start, int end, std::unordered_set <int>& nodes, Graph& graph) {
| ^
indcyc.cpp:184:140: error: a function-definition is not allowed here before '{' token
184 | void dfs(int& node, int& root, std::unordered_set <int>& nodes, std::unordered_set <int>& g, std::unordered_set <int>& ngh, Graph& graph) {
| ^
indcyc.cpp:217:45: error: a function-definition is not allowed here before '{' token
217 | void solve(std::unordered_set <int>& nodes) {
| ^
indcyc.cpp:248:11: error: a function-definition is not allowed here before '{' token
248 | int main(){
| ^
indcyc.cpp:145:7: warning: unused variable 'visited' [-Wunused-variable]
145 | bool* visited;
| ^~~~~~~
indcyc.cpp: In function 'void solve(std::unordered_set<int>&)':
indcyc.cpp:308:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::unordered_set<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
308 | for(int i = 0; i < nextNodes.size(); i ++)
| ~~^~~~~~~~~~~~~~~~~~
indcyc.cpp:283:32: warning: unused variable 'V' [-Wunused-variable]
283 | int root = *nodes.begin(), V = graph.V;
| ^
