#include <bits/stdc++.h>
#define N 100005 ///the maximum number of nodes in the graph
#define inf 200000000
using namespace std;
ifstream fin("disjoint.in");
ofstream fout("disjoint.out");
queue<int> q; //to add nodes at bfs
int ctComponents = 0; //strongly connected components
vector<int> comp[N]; //to print the strongly connected components
struct edge {
int x, y, cost;
};
typedef pair < int, int > Pair; // define our pair for an easier use
class Graph {
private:
int n, m;
vector<int> adlist[N]; //adjent list
vector < Pair > adj_cost[N]; ///USED FOR DIJKSTRA & bellmanford : the adjent list for cost
///ad[x] = (y,c) where c = cost for the edge from x->y
priority_queue < Pair, vector < Pair >, greater < Pair > > queue_edges; ///add (for used edges in ascending order of their costs)
///pair(cost, node) where cost = source->node
///for DIJKSTRA
edge edges[N];
bool viz[N] = {0};
int dist[N] = {0}; //the minuimum distance from a particular vertex to all others in BFS
stack<int> s; //final times in dfs
void dfCritical(int k, int father, int level[], int level_min[], vector<vector<int>>& sol); // dfs used in the algorithm for critical edges
void dfBiconnected(int k, int father, int level[N], int level_min[N], vector<vector<int>> &biconnected, pair<int, int> stackk[], int &vf_stack); //dfs used in the algorithm for biconnected components
int representant(int node, int repres[N]); //finding the root for the tree where is part node
void reunite(int x, int y, int h[N], int repres[N]); //union 2 trees for apm
friend bool compare(edge A, edge B);//to compare costs of 2 edges
public:
Graph() = default;
Graph(int n, int m):n(n), m(m){}
void readDirected();
void readUndirected();
void readUndirectedCost();
void readDirectedCost();
void bfs(int first); //for minimum path
void dfs(int first); //for connected components
void dfsT(int first); //used only for Transpoused --> do not add nodes in s, print the node
//we will use "viz" from the transpoused graph
void printDist();
void connectedComponents();
void printGraph();
Graph transpose();
void stronglyConnectedComponents();
void sortTopo(); //dfs and we keep the final times, after a node is finished, we put it in the stack
bool graphExistsHakimi(vector<int> &dg, int n); //the grades and number of nodes
void biconnectedComponents();
vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections); /*Input: n = 2, connections = [[0,1]] Output: [[0,1]]*/
void kruskal();
void disjoint();
void dijkstra();
void bellmanford();
};
void Graph::readDirected() {
for(int i = 1; i <= m; ++i) {
int x, y;
fin >> x >> y;
adlist[x].push_back(y);
}
}
void Graph::readUndirected() {
for(int i = 1; i <= m; ++i) {
int x, y;
fin >> x >> y;
adlist[x].push_back(y);
adlist[y].push_back(x);
}
}
void Graph::readUndirectedCost() {
for(int i = 1; i <= m; ++i) {
int x, y, cost;
fin >> x >> y >> cost;
adlist[x].push_back(y);
adlist[y].push_back(x);
edges[i].x = x;
edges[i].y = y;
edges[i].cost = cost;
}
}
void Graph::readDirectedCost() {
for(int i = 1; i <= m; ++i) {
int x, y, cost;
fin >> x >> y >> cost;
adj_cost[x].push_back(make_pair(y,cost));
}
}
void Graph::printGraph() {
for(int i = 1; i <= n; ++i) {
fout << i <<":";
for(int j = 0; j < adlist[i].size(); ++j)
fout << adlist[i][j] << " ";
fout <<"\n";
}
}
void Graph::bfs(int first) {
///bfs detemines the shortest path
int node, dim;
dist[first] = 1;
viz[first] = 1;
q.push(first);
while(!q.empty()) //for each node add all his neighbors that haven't been visisted yet & update minimum distance
{
node = q.front();
q.pop();
dim = adlist[node].size();
for(int i = 0; i < dim; ++i)
if(!viz[adlist[node][i]])
{
cout << adlist[node][i] <<" ";
viz[adlist[node][i]] = 1;
dist[adlist[node][i]] = dist[node] + 1;
q.push(adlist[node][i]);
}
}
}
void Graph::dfs(int node) {
int i, dim;
viz[node] = 1;
dim = adlist[node].size();
for(i = 0; i < dim; ++i)
if(!viz[adlist[node][i]])//contiune the dfs from the new node
dfs(adlist[node][i]);
s.push(node); //after we finish with a node --> we add it in the stack --> "final times"
}
void Graph::printDist() {
int i;
for(i = 1; i <= n; ++i)
fout << dist[i] - 1 << " ";
}
void Graph::connectedComponents() {
///a crossing with a dfs is a connected component
int i, nr = 0;
for(i = 1; i <= n; ++i)
if(!viz[i]) //we found another component
{
nr++;
dfs(i);
}
fout << nr;
}
void Graph::dfsT(int node){
int i, dim;
comp[ctComponents].push_back(node);//is part of the same component
viz[node] = 1;
dim = adlist[node].size();
for(i = 0; i < dim; ++i)
if(!viz[adlist[node][i]])
dfsT(adlist[node][i]);
}
Graph Graph::transpose() {
int i, j;
Graph gt(n, m);
for(i = 1; i <= n; ++i)
for(j = 0; j < adlist[i].size(); ++j)
gt.adlist[adlist[i][j]].push_back(i);
return gt;
}
void Graph::stronglyConnectedComponents() {
///1 g transpouse = gt
///2 dfs g --> end times --> add in stack
///3 dfs on gt in descending order of end times(just substract from the stack)
///the nodes from a crossing = strongly connected component
int node;
for(int i = 1; i <= n; ++i)
if(!viz[i])
this->dfs(i);
Graph gt = this->transpose();
while(!s.empty()) //dfs on gt in reverse order of the final times
{
node = s.top();
s.pop();
if(!gt.viz[node])//a crossing with dfs means a strongly connected component
{
ctComponents++;
gt.dfsT(node);
}
}
int i, j;
fout << ctComponents << "\n";
for(i = 1; i <= ctComponents; ++i) {
for(j = 0; j < comp[i].size(); ++j)
fout <<comp[i][j] << " ";
fout << "\n";
}
}
void Graph::sortTopo() {
///condition : if exist edge u-->v then u is BEFORE v in topological sort
///determine the end times with dfs --> add them in a stack --> our solution
///if exist u->v ==> end_time[u] > end_time[v]
for(int i = 1; i <= n; ++i)
if(!viz[i])
dfs(i);
while(!s.empty())
{
fout << s.top() <<" ";
s.pop();
}
}
bool Graph::graphExistsHakimi(vector<int> &dg, int n) {
///sort the vector of degrees desc
///we start with the biggest degree v ant link it with the next v nodes (substract 1 from the next v elements)
///repeat until:
///1. all the remaining elements are 0 (graph exists)
///2. negative values encounter after substraction (doesn't exist)
///3. not enough elements remaining after substraction (doesn't exist)
while(1) ///mai eficient count sort!!!
{
sort(dg.begin(), dg.end(), greater<>());
if(dg[0] == 0)
return true; //all elements equal to 0
int degree = dg[0];
dg.erase(dg.begin() + 0); //delete the first element
if(degree > dg.size())//check if enough elements are in the list
return false;
for(int i = 0; i < dg.size(); ++i) //substract 1 from the following
{
dg[i]--;
if(dg[i] < 0) //check negative
return false;
}
}
}
void Graph::dfCritical(int k, int father, int level[], int level_min[], vector<vector<int>>& sol) {
///dfs and keep the level and minimum level that we can reach from a node
///when we find " level[k] < level_min[node] " where node = child, it means that we need that edge to reach the ancestors--> critical edge
if( father == -1)
level[k] = 1;
else
level[k] = level[father] + 1;
level_min[k] = level[k];
int dim = adlist[k].size();
for (int i = 0; i < dim; ++i)
{
int node = adlist[k][i];
if(level[node])//if visited
{
if(node != father && level[node] < level_min[k]) //return edge --> check if we can reach a higher level
level_min[k] = level[node];
}
else
{
dfCritical(node, k, level, level_min, sol); //continue dfs
if(level_min[k] > level_min[node]) //one of the childs has a return edge
level_min[k] = level_min[node];
///determine critical connections
if(level[k] < level_min[node]) //we can not reach that level or a higher level with a return edge
{
vector<int> current;
current.push_back(node);
current.push_back(k);
sol.push_back(current);
}
}
}
}
vector<vector<int>> Graph :: criticalConnections(int n, vector<vector<int>>& connections) {
int level[N] = {0};
int level_min[N] = {0};
for(int i = 0; i < connections.size(); ++i)//for each edge
{
adlist[connections[i][0]].push_back(connections[i][1]);
adlist[connections[i][1]].push_back(connections[i][0]);
}
vector<vector<int>> sol;//solution of critical edges
dfCritical(0, -1, level, level_min, sol);
return sol;
}
void Graph::biconnectedComponents() {
///dfs and keep adding nodes in the stack until we finish the biconnected component
///keep the level and minimum level that we can reach from a node
///when we find " level_min[node] >= level[k] " where node = child, k = father we have to substract all the elements until k from the stack --> a new biconnected component
int level[N] = {0};
int level_min[N] = {0};
vector<vector<int>> biconnected;//vector with the components
pair<int, int> stackk[N * 2];// a stack with the nodes visited in dfs(added by their edges)
// we have to keep edges bcs the articulation points are part of more biconnecte components
int vf_stack = 0;
dfBiconnected(1, 0, level, level_min, biconnected, stackk, vf_stack);
fout << biconnected.size() << "\n";
for(int i = 0; i < biconnected.size(); ++i)
{
vector <int> comp = biconnected[i];
for(int j = 0 ; j < comp.size(); ++j)
fout << comp[j] <<" ";
fout <<"\n";
}
}
void Graph::dfBiconnected(int k, int father, int level[N], int level_min[N], vector<vector<int>> &biconnected, pair<int, int> stackk[], int &vf_stack) {
level[k] = level[father] + 1;
level_min[k] = level[k];
int dim = adlist[k].size();
for (int i = 0; i < dim; ++i)
{
int node = adlist[k][i];
if(level[node])//if visited
{
if(node != father && level[node] < level_min[k]) //return edge --> check if we can reach a higher level
level_min[k] = level[node];
}
else
{
stackk[++vf_stack] = {k, node}; //add in dfs order
dfBiconnected(node, k, level, level_min, biconnected, stackk, vf_stack); //continue dfs
if(level_min[k] > level_min[node]) //one of the childs has a return edge
level_min[k] = level_min[node];
if(level_min[node] >= level[k]) //the condition that the biconnected component is complete
{
biconnected.push_back({}); //create e new biconnected component
while(stackk[vf_stack].first != k) //add all nodes from the stack until k
biconnected.back().push_back(stackk[vf_stack--].second); //add at the last component the nodes
biconnected.back().push_back(stackk[vf_stack].second);
biconnected.back().push_back(stackk[vf_stack].first); //add for the last edge both nodes the articulation point is part of more components
vf_stack--;
}
}
}
}
bool compare(edge A, edge B) {
return A.cost < B.cost;
}
int Graph::representant(int node, int repres[N]) {
while(repres[node] != 0) //father -> father >>searching for root
node = repres[node];
return node;
}
void Graph:: reunite(int x, int y, int h[N], int repres[N]){ ///the smaller tree becomes child
int repres1 = representant(x, repres);
int repres2 = representant(y, repres);
if(h[repres1] < h[repres2])
{
h[repres2] += h[repres1];
repres[repres1] = repres2;
}
else{
h[repres1] += h[repres2];
repres[repres2] = repres1;
}
}
void Graph::kruskal(){
vector<pair<int, int>>sol; //to memorate the edges
int total_cost = 0; //the solution
int h[N] = {0}; //h[x] = height of the tree with the root x
int repres[N] = {0}; //the representant of a tree
sort(this->edges + 1, this->edges + m + 1, compare);
//initialization
//for(int i = 1; i <= n; ++i)
// repres[i] = h[i] = 0;
for(int i = 1; i <= m && sol.size() != n-1; ++i)//for each edge until we choose n-1
{
int repres1 = representant(edges[i].x, repres);
int repres2 = representant(edges[i].y, repres);
if(repres1 != repres2) //if they are not part of the same component
{
total_cost += edges[i].cost;
sol.push_back(make_pair(edges[i].x, edges[i].y));
reunite(repres1, repres2, h, repres);
}
}
fout << total_cost << "\n" << sol.size() <<"\n";
for(int i = 0; i < sol.size(); ++i)
fout << sol[i].first << " " << sol[i].second << "\n";
}
void Graph::disjoint(){
int h[N] = {0}; //h[x] = height of the tree with the root x
int repres[N] = {0}; //the representant of a tree
for(int i = 1; i <= m; ++i)
{
int x, y, task;
fin >> task >> x >> y;
if(task == 1)
reunite(x, y, h, repres);
else
{
int repres1 = representant(x, repres);
int repres2 = representant(y, repres);
if(repres1 != repres2)
fout << "NU\n";
else fout << "DA\n";
}
}
}
void Graph::dijkstra(){
for(int i = 1; i <= n; ++i)
dist[i] = inf;
int source = 1; //the start node
queue_edges.push(make_pair(0, source)); ///the cost is 0 to arrive at the source
dist[source] = 0;
while(!queue_edges.empty())//we will add in the queue all the updated paths (cost, node) --> priority queue ordered by their costs
{ //at a momemnt we will choose the minimum cost existent
int node = queue_edges.top().second;
queue_edges.pop();
if(viz[node] == 1)continue; //skip this node bcs we already had a path to it
else viz[node] = 1; //continue from this node
for(int i = 0; i < adj_cost[node].size(); ++i)//for all nodes that "node" is connected to
{
int vertex = adj_cost[node][i].first;
int cost = adj_cost[node][i].second;
//try to update minimum cost
if(cost + dist[node] < dist[vertex])
{
dist[vertex] = dist[node] + cost;
queue_edges.push(make_pair(dist[vertex], vertex));
}
}
}
for(int i = 2; i <= n; ++i)
if(dist[i] == inf)
fout << 0 << " ";
else fout << dist[i] << " ";
}
void Graph::bellmanford() {
///like Dijkstra but can contain negativ costs
///after k iterations --> will be calculated the costs for node, where exists a path of lg k source -> node
//d(k)[x] = the minimum cost with maximum k edges
//d(k)[y] = min { d(k)[y], min {d(k-1)[x] + xy | for each x that is connected to y}}
//at an iteration is enough to "relax" the edges from vertex that have already been updated --> queue
//if exists negativ circuit --> NO SOLUTION
// --> after n-1 steps still exists a vertex to be updated
bool exists = true;
int time_in_queue[N] = {0}; //for negativ circuit --> how many times a vertex is visitied
queue<int> queue_edges;
for(int i = 1; i <= n; ++i)
{
viz[i] = 0;
time_in_queue[i] = 0;
dist[i] = inf;
}
dist[1] = 0;
viz[1] = 1;
queue_edges.push(1);
while(!queue_edges.empty())
{
int node = queue_edges.front();
queue_edges.pop();
viz[node] = 0; //it is not in queue anymore
time_in_queue[node]++;
if(time_in_queue[node] >= n)
{
exists = false;
break;
}
for(int i = 0; i < adj_cost[node].size(); ++i) //for each neighbour
{
int vertex = adj_cost[node][i].first;
int cost = adj_cost[node][i].second;
if(dist[node] + cost < dist[vertex])//try to update minimum cost until vertex (with i edges)
{
dist[vertex] = dist[node] + cost;
if(viz[vertex] == 0) ////////////////////////////////////////////////////////////////////////////////////
queue_edges.push(vertex);
}
}
}
if(exists == false)
fout << "Ciclu negativ!";
else
for(int i = 2; i <= n; ++i)
fout << dist[i] << " ";
}
int main()
{
int i, first, n, m;
fin >> n >> m;
Graph g(n, m);
///MINIMUM DISTANCE
/*
g.readDirected();
g.bfs(first);
g.printDist();
*/
/// CONNECTED COMPONENTS
/*
g.readUndirected();
g.connectedComponents();
*/
///BICONNECTED COMPONENTS --> 90 -time limit exceeded && 100
/*
g.readUndirected();
g.biconnectedComponents();
*/
///STRONGLY CONNECTED COMPONENTS
///time limit exceeded 1 test
/*
g.readDirected();
g.stronglyConnectedComponents();
*/
///TOPOLOGICAL SORT
/*
g.readDirected();
g.sortTopo();
*/
///HAVEL-HAKIMI
/*
vector<int> dg;
fin >> n;
Graph g(n, 0);
for(int i = 1; i <= n; ++i)
{
fin >> first;
dg.push_back(first);
}
if(g.graphExistsHakimi(dg, n))
fout << "yes";
else fout << "no";
*/
///CRITICAL CONNECTIONS
/*
//fin >> n;
n = 2;
Graph g(n, 0);
vector<vector<int>>connections = {{0,1}};
vector<vector<int>> sol = g.criticalConnections(n, connections);
fout << sol.size() << "\n";
for(int i = 0; i < sol.size(); ++i)
{
for(int j = 0; j < sol[i].size(); ++j)
fout << sol[i][j] << " ";
fout <<"\n";
}
*/
///PARTIAL TREE WITH MINIMUM COST --> KRUSKAL
/*
g.readUndirectedCost();
g.kruskal();
*/
///THE PATH WITH MINIMUM COST FROM A SPECIFIC NODE --> DIJKSTRA
/*
g.readDirectedCost();
g.dijkstra();
*/
///THE PATH WITH MINIMUM COST FROM A SPECIFIC NODE ( with negativ edges) --> BELLMANFORD
/*
g.readDirectedCost();
g.bellmanford();
*/
///DISJOINT --> UNION & FIND
g.disjoint();
return 0;
}
Lupascu Miruna-Stefania MirunaStefania