Pagini recente » Cod sursa (job #1769425) | Cod sursa (job #1566266) | Istoria paginii runda/noaptea_burlacilor2/clasament | Cod sursa (job #950702) | Cod sursa (job #2928772)
#include <iostream>
#include <vector>
#include <fstream>
#include <stack>
using namespace std;
int n, nr_ctc;
///construim un vector de vectori in care retinem nodurile pe care le contine fiecare componenta conexa
vector <vector <int>> sol;
vector <vector <int>> adj; ///lista adiacenta
vector <vector <int>> adj_t; ///lista adiacenta transpusa
vector <int> viz;
stack <int> st;
ifstream f("ctc.in");
ofstream g("ctc.out");
void afisare()
{
///afisam nr ctc
g<<nr_ctc<<"\n";
///aici afisam nodurile fiecarei ctc
for(int i=1; i <= nr_ctc ; i++)
{
for(auto v: sol[i])
{
g<< v <<" ";
}
g<<"\n";
}
}
void dfs(int nod)
{
for(auto i=0; i < adj[nod].size();i++)
{
if(viz[adj[nod][i]]==0)
{
viz[adj[nod][i]]=1;
dfs(adj[nod][i]);
}
}
/// introducem nodurile vizitate in dfs intr-o stiva pentru a putea aplica apoi dfs-ul transpus
st.push(nod);
}
void dfs_t(int nod)
{
///daca nodul e vizitat in ambele parcurgeri dfs, marcam in viz cu 2
viz[nod] = 2;
///adaugam nodul in solutie
sol[nr_ctc].push_back(nod);
///parcurgem nodurile vecine si daca au fost vizitate apelam df-ul trasnpus
for( auto i = 0 ;i < adj_t[nod].size(); i++)
{
if(viz[adj_t[nod][i]] == 1)
{
dfs_t(adj_t[nod][i]);
}
}
}
void face(int m)
{
for(int i=1; i <= m ; i++)
{ int a,b;
f>>a>>b;
adj[a].push_back(b);
adj_t[b].push_back(a);
}
}
int main()
{
int n, m;
f>>n>>m;
sol.resize(n+1);
viz.resize(n+1,0);
adj.resize(n+1);
adj_t.resize(n+1);
face(m);
///marcam daca nodurile au fost vizitate sau nu atat in rpima cat si in a doua parcurgere
for(int i = 1; i <= n ; i++)
{ ///daca nodul nu a fost vizitat, atunci il marcam ca vizitat si apoi apelam functia dfs
if(viz[i] == 0)
{
viz[i]=1;
dfs(i);
}
}
///cat timp avem elemente in stiva, verificam daca nodul a fost vizitat in dfs, iar apoi apelam dfs-ul transpus
while(st.size() > 0)
{
int nod = st.top();
st.pop();
if(viz[nod]==1)
{
nr_ctc++;
dfs_t(nod);
}
}
afisare();
return 0;
}