| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 508783 | CraniXort | Potemkin cycle (CEOI15_indcyc) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
}