Pagini recente » Cod sursa (job #187897) | Cod sursa (job #597930) | Cod sursa (job #2762244) | Cod sursa (job #674645) | Cod sursa (job #2797536)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
#include <bits/stdc++.h>
using namespace std;
//ifstream fin("bfs.in");
//ofstream fout("bfs.out");
//ifstream fin("dfs.in");
//ofstream fout("dfs.out");
//ifstream fin("biconex.in");
//ofstream fout("biconex.out");
//ifstream fin("ctc.in");
//ofstream fout("ctc.out");
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
int viz[100001];
int first_value[100001];
int min_pos[100001];
stack <int> node_order;
int counter=0;
vector<int>biconex[100001];
vector<int>ctc[100001];
vector<int>sol_ctc[100001];
vector<int>sol_sortaret;
class grafMare
{
int N,M;
vector <int> graf[100001];
public:
grafMare(){};
int get_N();
void citireBFS();
void citireDFS();
void actualDFS(int);
void citire_biconex();
void add_a_biconex(int,int);
void DFS_biconex(int,int,int);
void citireCTC();
void DFS_CTC_1(int);
void DFS_CTC_2(int);
void citire_top();
void DFS_top(int);
};
void grafMare::DFS_top(int current_node)
{
viz[current_node]=1;
for(auto x : graf[current_node])
if(!viz[x])
DFS_top(x);
sol_sortaret.push_back(current_node);
}
void grafMare::citire_top()
{
fin>>N>>M;
for(int i=0;i<M;i++)
{
int a,b;
fin>>a>>b;
graf[a].push_back(b);
}
for(int i=1;i<=N;i++)
if(!viz[i])
DFS_top(i);
reverse(sol_sortaret.begin(),sol_sortaret.end());
for(auto x : sol_sortaret)
fout<<x<<" ";
}
void grafMare::citireCTC()
{
fin>>N>>M;
for(int i=0;i<M;i++)
{
int a,b;
fin>>a>>b;
graf[a].push_back(b);
ctc[b].push_back(a);
}
for(int i=1;i<=N;i++)
if(!viz[i])
DFS_CTC_1(i);
while(!node_order.empty())
{
if(viz[node_order.top()]==1)
{
counter++;
DFS_CTC_2(node_order.top());
}
node_order.pop();
}
fout<<counter<<"\n";
for(int i=1;i<=counter;i++)
{
for(auto x : sol_ctc[i])
fout<<x<<" ";
fout<<"\n";
}
}
void grafMare::DFS_CTC_1(int current_node)
{
viz[current_node]=1;
for(auto x : graf[current_node])
if(!viz[x])
DFS_CTC_1(x);
node_order.push(current_node);
}
void grafMare::DFS_CTC_2(int current_node)
{
viz[current_node]=2;
sol_ctc[counter].push_back(current_node);
for(auto x : ctc[current_node])
if(viz[x]==1)
DFS_CTC_2(x);
}
int grafMare::get_N()
{
return N;
}
void grafMare::citire_biconex()
{
fin>>N>>M;
for(int i=0;i<M;i++)
{
int a,b;
fin>>a>>b;
graf[a].push_back(b);
graf[b].push_back(a);
}
}
void grafMare::DFS_biconex(int current_node, int current_pos, int tata_node)
{
min_pos[current_node]=current_pos;
first_value[current_node]=current_pos;
node_order.push(current_node);
for(auto i : graf[current_node])
{
if(!min_pos[i]) //dfs
{
DFS_biconex(i, current_pos+1, current_node);
min_pos[current_node]=min(min_pos[current_node],min_pos[i]);
// actualizez levelul minim in caz ca baiatul urmator are traseu mai scurt de la un nod mai devreme, dupa ce intra in else if(desen 2, 7-8, 1-8)
if(min_pos[i] >= current_pos) // asta e punct de articulatie, daca n ar respecta cond asta, ins ca exista alt traseu care mentine conditia cu conex
{
counter++;
//current_node e first si i duce la ult elem din stack
while(node_order.top()!=i)
{
biconex[counter].push_back(node_order.top());
node_order.pop();
}
biconex[counter].push_back(node_order.top());
node_order.pop();
biconex[counter].push_back(current_node);
}
}
else if(i!=tata_node)
min_pos[current_node]=min(min_pos[current_node],first_value[i]);
}
}
void grafMare::citireBFS()
{
fin>>N>>M;
int start;
fin>>start;
int a,b;
for(int i=0;i<M;i++)
{
fin>>a>>b;
graf[a].push_back(b);
}
int sol[100001];
for(int i=0;i<N+1;i++)
sol[i]=-1;
queue <int> q;
q.push(start);
sol[start]=0;
while(!q.empty())
{
int first=q.front();
q.pop();
for(int vecin : graf[first])
{
if(sol[vecin]==-1)
{
sol[vecin]=sol[first]+1;
q.push(vecin);
}
}
}
for(int i=1;i<N+1;i++)
fout<<sol[i]<<" ";
}
void grafMare::actualDFS(int index)
{
for(int vecin : graf[index])
if(!viz[vecin])
{
viz[vecin]=1;
actualDFS(vecin);
}
}
void grafMare::citireDFS()
{
fin>>N>>M;
int start=1;
int a,b;
for(int i=0;i<M;i++)
{
fin>>a>>b;
graf[a].push_back(b);
graf[b].push_back(a);
}
for(int i=0;i<N+1;i++)
viz[i]=0;
for(int i=1;i<N+1;i++)
if(!viz[i])
{
counter++;
actualDFS(i);
}
fout<<counter;
}
int main()
{
grafMare gm;
//gm.citireBFS();
gm.citire_top();
}