Pagini recente » Cod sursa (job #66710) | Cod sursa (job #255225) | Cod sursa (job #2369532) | Cod sursa (job #830446) | Cod sursa (job #2927458)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
void constr_list(int n, int m, vector<vector<int>> &l_a, vector<vector<int>> &l_a_t)
{
std::vector<int> t; //lista vida
for (int j = 0; j <= n; j++) l_a.push_back(t), l_a_t.push_back(t); //imi initializez lista de liste cu n liste vide
for (int i = 1; i <= m; i++){
int vf1, vf2;
fin>>vf1>>vf2;
l_a[vf1].push_back(vf2);
l_a_t[vf2].push_back(vf1);
}
}
void DFS(int d, vector<int> &vizit, vector<vector<int>> list_a, stack<int> &st)
{
vizit[d] = 1;
for (int i = 0; i < list_a[d].size(); i++){
if (!vizit[list_a[d][i]]){
DFS(list_a[d][i], vizit, list_a, st);
}
}
st.push(d);
}
void DFS_trans(int d, int nr, vector<int> &vizit, vector<vector<int>> &comp, vector<vector<int>> l_a_t)
{
vizit[d] = 2;
comp[nr].push_back(d);
for (int i = 0; i < l_a_t[d].size(); i++){
if(vizit[l_a_t[d][i]] == 1){
DFS_trans(l_a_t[d][i], nr, vizit, comp, l_a_t);
}
}
}
int main() {
int n,m; //noduri/muchii
vector<vector<int>> list_adj; //lista de adiacenta pentru graful normal
vector<vector<int>> list_adj_trans; //lista de adiacenta pentru graful transpus
fin>>n>>m;
vector<int> vizit; //vectorul de noduri vizitate
for (int i = 0; i <= n; i++) vizit.push_back(0); //initializat cu 0
stack<int> stack;//stiva in care adaugam nodurile
constr_list(n, m, list_adj, list_adj_trans);
for (int i = 1; i <= n; i++){
if (!vizit[i]) DFS(i, vizit, list_adj, stack);
}
int nr_comp = 0;
vector<vector<int>> componente;
vector<int> empty;
componente.push_back(empty);
while(!stack.empty()){
int nod_curent = stack.top();
if (vizit[nod_curent] == 1){
nr_comp++;
componente.push_back(empty);
DFS_trans(nod_curent, nr_comp, vizit, componente, list_adj_trans);
}
stack.pop();
}
fout<<nr_comp<<"\n";
for (int i = 1; i <= nr_comp; i++){
for (auto it: componente[i]){
fout<<it<<" ";
}
fout<<"\n";
}
return 0;
}