/*
1. BFS: https://infoarena.ro/job_detail/2797641 (100p)
2. DFS: https://infoarena.ro/job_detail/2797186 (100p)
3. CTC: https://infoarena.ro/job_detail/2798894 (100p)
4. Havel Hakimi:
5. Sortare topologica: https://infoarena.ro/job_detail/2797863 (100p)
6. Critical connections: https://leetcode.com/submissions/detail/585217368/ (Accepted)
7. Binconexe: https://infoarena.ro/job_detail/2798875 (90p)
8. Bellmanford: https://infoarena.ro/job_detail/2809092 (100p)
9. Dijkstra: https://infoarena.ro/job_detail/2809102 (80p)
10. Paduri de multimi disjuncte: https://www.infoarena.ro/job_detail/2809108 (100p)
11. APM: https://www.infoarena.ro/job_detail/2809110 (90p)
12. RoyFloyd: https://infoarena.ro/job_detail/2812694 (100p)
13. Darb: https://infoarena.ro/job_detail/2812930 (100p)
14. Flux maxim: https://www.infoarena.ro/job_detail/2813299 (100p)
15. Cuplaj: https://www.infoarena.ro/job_detail/2820089 (100p)
*/
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#include <stack>
#include <algorithm>
#include <sstream>
#include <string.h>
using namespace std;
#define Nmax 100007
#define max 1024
#define Rezolvare 17
#define inf 1000000000
#define neg_inf 1000000000
#define NIL 0
const char iname[] = "distante.in";
const char oname[] ="distante.out";
vector<int> rev[Nmax];
vector<int> aux;
vector <int> deg;
queue <int> coada;
vector<int> visited;
vector<int> niv_min;
vector<int> nivel,parent;
stack<int> st;
vector<vector<int> > output;
vector< pair<int,int> > node_with_cost[Nmax];
int greutate[Nmax];
int parinte[Nmax];
vector< pair < int, pair <int,int> > > muchii;
int capacitate[max][max];
int flux[max][max];
//vector<int> la[Nmax];
vector <int> pairU;
vector <int> pairV;
vector <int> dist;
int indx;
vector <int> out[Nmax];
int visited_flux[max];
int tata[max];
int nod_final;
vector <pair <int,int> > arbore;
int numar_muchii;
int nr_conex;
ifstream f(iname);
ofstream g(oname);
class Graph{
public:
Graph(int n, int m);
~Graph();
virtual void add_muchie(int x, int y){}
protected:
vector<int> la[Nmax]; //lista de adiacenta;
int n,m; //numarul de noduri si numarul de muchii
};
class Undirected: public Graph{
public:
bool is_correct_graph(vector<int> grade);
Undirected(int n, int m=0);
~Undirected();
void add_muchie(int x,int y)
{
la[x].push_back(y);
la[y].push_back(x);
}
void dfs(int start,int visited[]);
void criticalConnections(vector<vector<int>>& connections);
void biconex();
int find(int x);
void unite(int x, int y);
int kruskall();
void dfs_darb(int start,int& maxCount);
private:
void dfs_critical(const int cur);
void util(const int cur,const int parent);
void dfs_util(int start, int count, int& maxCount,bool visited[]);
};
class Directed: public Graph{
public:
Directed(int n,int m);
~Directed();
void add_muchie(int x,int y);
void bfs(int start, int visited[],int dist[]);
void findCTC();
void reverse();
void topologic(vector <int>& deg);
void bellmanford(vector< pair<int,int> > node_with_cost[Nmax],int source);
vector<int> dijkstra(int source);
void roy_floyd(int dist[][102]);
int fluxmax();
int cuplaj();
private:
void dfs_plus(int i,stack<int> &my_stack,int visited[]);
void dfs_reverse(int i,vector <int>& aux,int visited[]);
int flux_bfs(int source, int sink);
bool bfs_cuplaj();
bool dfs_cuplaj(int u);
};
class Disjoint
{
private:
int n,m;
public:
Disjoint(int,int);
~Disjoint();
int find(int x);
void unite(int x, int y);
};
bool Undirected::is_correct_graph(vector<int> grade)
{
sort(grade.begin(),grade.end(),greater <int>());
while(grade[0]!=0)
{
int v=grade[0];
grade.erase(grade.begin()+0);
if(v>grade.size())
return false;
for(int i=0;i<v;i++)
{
grade[i]--;
if(grade[i]<0)
return false;
}
sort(grade.begin(),grade.end(),greater <int>());
}
return true;
}
void Undirected::dfs_darb(int start,int& maxCount)
{
bool visited[n+1];
for(int i=0;i<n+1;i++)
visited[i]=false;
int count=0;
dfs_util(start,count+1,maxCount,visited);
}
void Undirected::dfs_util(int start, int count, int& maxCount,bool visited[])
{
visited[start] = true;
count++;
for(auto vecin: la[start])
{
if(!visited[vecin]){
if(count>=maxCount)
{
maxCount = count;
nod_final = vecin;
}
dfs_util(vecin,count,maxCount,visited);
}
}
}
int Undirected::kruskall()
{
Disjoint grf(n,m);
int cost = 0;
sort(muchii.begin(),muchii.end());
for(auto muchie:muchii)
{
if(grf.find(muchie.second.second)!=grf.find(muchie.second.first))
{
grf.unite(muchie.second.second,muchie.second.first);
cost+=muchie.first;
numar_muchii ++;
arbore.push_back(make_pair(muchie.second.second,muchie.second.first));
}
}
return cost;
}
int Disjoint::find(int x)
{
if(parinte[x]==x) return x;
return parinte[x] = find(parinte[x]);
}
void Disjoint::unite(int x, int y)
{
int parinte_x = find(x);
int parinte_y = find(y);
if(parinte_x!=parinte_y)
{
if(greutate[parinte_x]<greutate[parinte_y])
swap(parinte_x,parinte_y);
parinte[parinte_y]=parinte_x;
greutate[parinte_x]+=greutate[parinte_y];
}
}
void Undirected::util(const int cur,const int parent)
{
static int time = 0;
niv_min[cur] = nivel[cur] = ++time;
st.push(cur);
for(int j:la[cur])
{
if(!niv_min[j])
{
util(j,cur);
niv_min[cur] = min(niv_min[cur],niv_min[j]);
if(niv_min[j] >= nivel[cur])
{
indx++;
while(st.top()!=j){
out[indx].push_back(st.top());
st.pop();
}
out[indx].push_back(st.top());
st.pop();
out[indx].push_back(cur);
}
}
else
if(j != parent)
{
niv_min[cur]=min(niv_min[cur],nivel[j]);
}
}
}
void Undirected::biconex()
{
nivel.assign(n+1,-1);
niv_min.resize(n+1);
for(int i=0;i<n;i++)
{
if(!niv_min[i]){
util(i,0);
}
}
}
void Undirected::dfs_critical(int cur)
{
static int time=0;
visited[cur] = 1;
niv_min[cur] = nivel[cur] = ++time;
for(int j:la[cur])
{
if(!visited[j])
{
parent[j] = cur;
dfs_critical(j);
niv_min[cur] = min(niv_min[cur],niv_min[j]);
if(niv_min[j]>nivel[cur])
{
output.push_back({cur,j});
}
}
else
if(j!=parent[cur])
{
niv_min[cur]=min(niv_min[cur],nivel[j]);
}
}
}
void Undirected::criticalConnections(vector<vector<int>>& connections) {
n=this->n;
parent.assign(n+1,-1);
visited.assign(n+1,0);
niv_min.resize(n+1);
nivel.resize(n+1);
for(int i = 0; i < connections.size(); i++)
{
la[connections[i][0]].push_back(connections[i][1]);
la[connections[i][1]].push_back(connections[i][0]);
}
for(int i=0;i<n;i++)
{
if(visited[i]==0){
dfs_critical(i);
}
}
for(int i=0;i<output.size();i++)
cout<<output[i][0]<<" "<<output[i][1]<<endl;
}
void Undirected::dfs(int start,int visited[])
{
visited[start] = nr_conex;
for(auto i:la[start])
{
if(!visited[i])
dfs(i,visited);
}
}
int Directed::flux_bfs(int source, int sink)
{
queue<int> coada;
for(int i=0;i<=n+1;i++)
{
visited_flux[i] = 0;
}
visited_flux[source]=1;
coada.push(source);
tata[sink] = 0;
while(!coada.empty()){
int cur = coada.front();
coada.pop();
if(cur == sink) continue;
for(auto vecin: la[cur])
{
if(capacitate[cur][vecin] - flux[cur][vecin]>0 && !visited_flux[vecin]){
visited_flux[vecin]=1;
coada.push(vecin);
tata[vecin]=cur;
}
}
}
return (tata[sink]?true:false);
}
int Directed::fluxmax()
{
int rasp = 0;
for(int i=0;i<=n+1;i++)
{
tata[i] = 0;
}
while(flux_bfs(1,n)){
for(auto vecin:la[n])
{
if(flux[vecin][n]!=capacitate[vecin][n] && visited_flux[vecin])
{
tata[n]=vecin;
int fmin = inf;
int nod=n;
while(nod!=1)
{
if(capacitate[tata[nod]][nod]-flux[tata[nod]][nod]<fmin)
fmin = capacitate[tata[nod]][nod]-flux[tata[nod]][nod];
nod = tata[nod];
}
if(fmin==0) continue;
nod=n;
while(nod!=1)
{
flux[tata[nod]][nod] += fmin;
flux[nod][tata[nod]] -= fmin;
nod = tata[nod];
}
rasp += fmin;
}
}
}
return rasp;
}
void Directed::roy_floyd(int dist[][102])
{
for(int k = 1; k<=n; k++)
for(int i=1;i<=n;i++)
for(int j=1; j<=n;j++)
if(dist[i][k] && dist[k][j] && (dist[i][j]> dist[i][k] + dist[k][j] || !dist[i][j]) && i!=j)
dist[i][j] = dist[i][k] + dist[k][j];
}
void Directed::topologic(vector <int>& deg)
{
for(int i=1;i<=n;i++)
if(!deg[i]) coada.push(i);
while(!coada.empty())
{
for(auto j:la[coada.front()])
{
deg[j]--;
if(!deg[j]) coada.push(j);
}
g<<coada.front()<<" ";
coada.pop();
}
}
void Directed::dfs_reverse(int i,vector <int>& aux,int visited[])
{
visited[i]=1;
for(auto j:rev[i])
{
if(!visited[j])
dfs_reverse(j,aux,visited);
}
aux.push_back(i);
}
void Directed::findCTC()
{
int visited[n];
vector< vector<int> > sol;
for(int i=1;i<=n;i++)
visited[i]=0;
stack<int> my_stack;
for(int i=1;i<=n;i++)
if(!visited[i])
dfs_plus(i,my_stack,visited);
for(int i=1;i<=n;i++)
visited[i]=0;
while(!my_stack.empty())
{
int cur = my_stack.top();
my_stack.pop();
if(!visited[cur])
{
aux = vector<int>();
dfs_reverse(cur,aux,visited);
sol.push_back(aux);
}
}
g<<sol.size()<<"\n";
for(int i=0;i<sol.size();i++)
{
for(int j=0;j<sol[i].size();j++)
g<<sol[i][j]<<" ";
g<<"\n";
}
}
void Directed::reverse()
{
for(int i=1;i<=n;i++)
{
for(int j:la[i])
rev[j].push_back(i);
}
}
void Directed::dfs_plus(int i,stack<int> &my_stack,int visited[])
{
visited[i]=1;
for(int j:la[i])
{
if(!visited[j])
dfs_plus(j,my_stack,visited);
}
my_stack.push(i);
}
void Directed::add_muchie(int x,int y)
{
la[x].push_back(y);
}
void Directed::bfs(int start, int visited[],int dist[]){
queue <int> coada;
visited[start]=true;
coada.push(start);
dist[start] = 0;
while(!coada.empty())
{ start = coada.front();
coada.pop();
for(auto i:la[start])
{
if(!visited[i])
{
visited[i] = true;
coada.push(i);
dist[i]=dist[start]+1;
}
}
}
}
void Directed::bellmanford(vector< pair<int,int> > node_with_cost[Nmax],int source)
{
vector<int> dist(n+1,inf);
queue<int> q;
vector<int> cnt(n+1,0);
vector<bool> inqueue(n+1,false);
dist[source]=0;
q.push(source);
inqueue[source]=true;
while(!q.empty())
{
int u = q.front();
q.pop();
inqueue[u] = false;
for(auto neighbour:node_with_cost[u])
{
int v = neighbour.first;
int weight = neighbour.second;
if(dist[u]+weight<dist[v]){
dist[v] = dist[u]+weight;
if(!inqueue[v])
{
q.push(v);
inqueue[v] = true;
cnt[v]++;
if(cnt[v]>n)
{
g<<"Ciclu negativ!";
return;
}
}
}
}
}
for(int i=2;i<=n;i++)
g<<dist[i]<<" ";
}
vector<int> Directed::dijkstra(int source)
{
vector<int> dist(n+1,inf);
vector<bool> visited(n+1,false);
priority_queue<pair<int,int>,vector<pair<int,int>>,greater< pair<int,int> > > pq;
dist[source]=0;
pq.push(make_pair(0,source));
while(!pq.empty())
{
int u=pq.top().second;
pq.pop();
if(visited[u]) continue;
visited[u]=true;
for(auto i=node_with_cost[u].begin();
i!=node_with_cost[u].end();++i)
{
int v=(*i).first;
int weight = (*i).second;
if(!visited[v])
if(dist[v]>dist[u]+weight)
{
dist[v]=dist[u]+weight;
pq.push(make_pair(dist[v],v));
}
}
}
// for(int i=1;i<=n;i++)
// if(dist[i]!=inf)
// g<<dist[i]<<" ";
// else g<<0<<" ";
// g<<endl;
return dist;
}
bool Directed::bfs_cuplaj()
{
queue<int> coada;
for(int i=1;i<=n;i++)
{
//daca nodul e liber
if(pairU[i]==NIL)
{
dist[i]=0;
coada.push(i);
}
else dist[i]=inf;
}
dist[NIL]=inf;
while(!coada.empty())
{
int cur = coada.front();
coada.pop();
if(dist[cur]<dist[NIL])
{
for(auto v:la[cur])
{
if(dist[pairV[v]]==inf)
{
dist[pairV[v]] = dist[cur]+1;
coada.push(pairV[v]);
}
}
}
}
return (dist[NIL]!=inf);
};
bool Directed::dfs_cuplaj(int u)
{
if(u!=0)
{
for(auto v:la[u])
{
if(dist[pairV[v]] == dist[u]+1)
{
if(dfs_cuplaj(pairV[v])==true)
{
pairV[v]=u;
pairU[u]=v;
return true;
}
}
}
dist[u]=inf;
return false;
}
return true;
}
int Directed::cuplaj()
{
int e=n+m;
pairU.resize(n+1,NIL);
pairV.resize(m+1,NIL);
dist.resize(e+1,NIL);
int result=0;
while(bfs_cuplaj()) //cat timp exista o augmentare
{
for(int i=1;i<=n;i++)
if(pairU[i] == 0 && dfs_cuplaj(i))
result++;
}
return result;
}
Graph::Graph(int n=0, int m=0):n(n),m(m)
{
}
Graph::~Graph()
{
}
Undirected::Undirected(int n, int m): Graph(n,m)
{
}
Undirected::~Undirected()
{
}
Directed::Directed(int n, int m): Graph(n,m)
{
}
Directed::~Directed()
{
}
Disjoint::Disjoint(int n, int m): n(n),m(m){}
Disjoint::~Disjoint(){}
int main()
{
int n,m,s;
int x,y;
switch(Rezolvare)
{
case 1:
{
f>>n>>m>>s;
Directed grf(n,m);
for(int i=0;i<m;i++)
{
f>>x>>y;
grf.add_muchie(x,y);
}
f.close();
int visited[n],dist[n];
for(int i=0;i<=n;i++)
visited[i]=dist[i]=0;
grf.bfs(s,visited,dist);
for(int i=1;i<=n;i++)
{
if(visited[i])
g<<dist[i]<<" ";
else g<<-1<<" ";
}
break;
}
case 2:
{
f>>n>>m;
Undirected grf(n,m);
int visited[n];
for(int i=0;i<m;i++)
{
f>>x>>y;
grf.add_muchie(x,y);
}
for(int i=0;i<=n;i++)
visited[i]=0;
for(int i=1;i<=n;i++)
if(!visited[i])
{
nr_conex++;
grf.dfs(i,visited);
}
g<<nr_conex;
break;
}
case 3:
{
f>>n>>m;
Directed grf(n,m);
for(int i=0;i<m;i++)
{
f>>x>>y;
grf.add_muchie(x,y);
}
grf.reverse();
grf.findCTC();
break;
}
case 4:
{
vector<int> check;
int number;
cin>>number;
for(int i=0;i<number;i++)
{
int c;
cin>>c;
check.push_back(c);
}
Undirected grf(n);
if(grf.is_correct_graph(check))
cout<<"DA";
else cout<<"NU";
break;
}
case 5:
{
f>>n>>m;
Directed grf(n,m);
deg = vector<int>(n+1,0);
for(int i=0;i<m;i++)
{
f>>x>>y;
grf.add_muchie(x,y);
deg[y]++;
}
f.close();
grf.topologic(deg);
break;
}
case 6:
{
Undirected grf(4,0);
vector<vector<int> > connections;
connections.push_back({0,1});
connections.push_back({1,2});
connections.push_back({2,0});
connections.push_back({1,3});
grf.criticalConnections(connections);
break;
}
case 7:
{
f>>n>>m;
Undirected grf(n,m);
for(int i=0;i<m;i++)
{
f>>x>>y;
grf.add_muchie(x,y);
}
f.close();
grf.biconex();
g<<indx<<endl;
for(int i=1;i<=indx;i++)
{
for(auto j:out[i])
g<<j<<" ";
g<<endl;
}
break;
}
case 8:
{
f>>n>>m;
Directed grf(n,m);
for(int i=0;i<m;i++)
{
f>>x>>y>>s;
node_with_cost[x].push_back(make_pair(y,s));
}
f.close();
grf.bellmanford(node_with_cost,1);
break;
}
case 9:
{
f>>n>>m;
Directed grf(n,m);
for(int i=0;i<m;i++)
{
f>>x>>y>>s;
node_with_cost[x].push_back(make_pair(y,s));
node_with_cost[y].push_back(make_pair(x,s));
}
f.close();
grf.dijkstra(1);
break;
}
case 10:
{
f>>n>>m;
for(int i=1;i<=n;i++){
parinte[i]=i;
greutate[i]=1;
}
Disjoint grf(n,m);
for(int i=0;i<m;i++)
{
f>>s>>x>>y;
if(s==1)
{
grf.unite(x,y);
}
else
{
if(grf.find(x)==grf.find(y))
g<<"DA\n";
else g<<"NU\n";
}
}
f.close();
break;
}
case 11:
{
f>>n>>m;
for(int i=1;i<=n;i++){
parinte[i]=i;
greutate[i]=1;
}
Undirected grf(n,m);
for(int i=0;i<=m;i++)
{
f>>x>>y>>s;
muchii.push_back(make_pair(s,make_pair(x,y)));
}
f.close();
g<<grf.kruskall()<<"\n";
g<<numar_muchii<<"\n";
for(int i=0;i<numar_muchii;i++)
g<<arbore[i].first<<" "<<arbore[i].second<<"\n";
break;
}
case 12:
{
int pondere[102][102];
f>>n;
Directed grf(n,0);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
f>>pondere[i][j];
}
grf.roy_floyd(pondere);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)
g<<pondere[i][j]<<" ";
g<<"\n";
}
break;
}
case 13:
{
f>>n;
m = n-1;
Undirected grf(n,m);
for(int i=0;i<m;i++)
{
f>>x>>y;
grf.add_muchie(x,y);
}
f.close();
int maxCount = neg_inf;
grf.dfs_darb(1,maxCount);
grf.dfs_darb(nod_final,maxCount);
g<<maxCount;
break;
}
case 14:
{
int x,y,s;
f>>n>>m;
Directed grf(n,m);
for(int i=0;i<m;i++)
{
f>>x>>y>>s;
capacitate[x][y] = s;
grf.add_muchie(x,y);
grf.add_muchie(y,x);
}
f.close();
g << grf.fluxmax()<< endl;
break;
}
case 15:
{
int e;
f>>n>>m>>e;
Directed grf(n,m);
for(int i=1;i<=e;i++){
f>>x>>y;
grf.add_muchie(x,y);
}
f.close();
g<<grf.cuplaj()<<"\n";
for(int i=1;i<=m;i++)
if(pairV[i]>0)
g<<pairV[i]<<" "<<i<<"\n";
}
case 16:
{
//rezolvarea cerintei senat-infoarena
//pentru a rezolva cerinta v-om avea nevoie de un cuplaj
//unde pairU (dreapta) sunt comisile
//pairV (stanga) sunt presedintii
f>>m>>n;
Directed grf(n,m);
string linie;
int i=0;
while(getline(f,linie))
{
stringstream ss(linie);
while(ss>>x)
{
grf.add_muchie(i,x);
}
i++;
}
int rez = grf.cuplaj();
if(rez!=n)
g<<0;
else
{
for(int i=1;i<=n;i++)
g<<pairU[i]<<endl;
}
break;
}
case 17:
{
//problema distante-infoarena
//idee: pentru calcularea distantelor folosim dijsktra
//facem asta pentru ca datele sunt pozitive
int numar_graf,cost;
int bronzarel[Nmax];
f>>numar_graf;
int source;
for(int i=1;i<=numar_graf;i++)
{
f>>n>>m>>source;
Directed grf(n,m);
for(int i=1;i<=n;i++)
{
f>>bronzarel[i];
node_with_cost[i].clear();
}
for(int i=0;i<m;i++)
{
f>>x>>y>>cost;
node_with_cost[x].push_back(make_pair(y,cost));
node_with_cost[y].push_back(make_pair(x,cost));
}
vector<int> bumbarel = grf.dijkstra(source);
int ok=1;
for(int i=1;i<=n;i++)
if(bumbarel[i]!=bronzarel[i])
{
ok=0;
g<<"NU\n";
break;
}
if(ok)
g<<"DA"<<"\n";
}
}
}
g.close();
return 0;
}
Stefania Cristea StefaniaCri