Pagini recente » Cod sursa (job #2520017) | Cod sursa (job #1015349) | Cod sursa (job #1022201) | Cod sursa (job #2381301) | Cod sursa (job #2932596)
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n,m;
vector<vector<int>> la;
vector<vector<int>> raspuns;
/*
O(n+m) , n = noduri, m = nr leg. , folosesc lista de adiacenta, alg lui tarjan
fac DFS, indexand mereu nodul la care ma aflu, si setandu-i indexul minim = el insusi,
atunci cand vad ca am legatura cu vreun nod din stiva, atunci se afla in aceeasi componenta conexa si atribui low cu minim-ul dintre ambele
verific daca id-ul nodului = low nodului respectiv => e inceputul componentei conexe si dau pop din stiva pana cand nodul curent este sters
*/
stack<int> stiva;
int low[100001],viz[100001],ctc[100001];
int id=1;
void citire()
{
f>>n>>m;
int i,x,y;
for(i=0;i<=n;i++)
{
vector<int> aux;
la.push_back(aux);
}
for(i=1;i<=m;i++)
{
f >> x >> y;
la[x].push_back(y);
}
for(i=1;i<=n;i++)
sort(la[i].begin(),la[i].end());
}
void dfs(int curent)
{
stiva.push(curent);
low[curent] = viz[curent] = id;
ctc[curent] = 1;
id++;
int i,l,dest,aux;
l = la[curent].size();
for(i=0;i<l;i++)
{
dest = la[curent][i];
if(viz[dest] == 0)
dfs(dest);
if(ctc[dest]==1)
low[curent] = min(low[curent],low[dest]);
}
if(viz[curent] == low[curent])
{
vector<int> octc;
aux = stiva.top();
ctc[aux]=0;
octc.push_back(aux);
stiva.pop();
while(aux != curent)
{
aux = stiva.top();
ctc[aux]=0;
octc.push_back(aux);
stiva.pop();
}
raspuns.push_back(octc);
}
}
void rezolvare()
{
int i;
for(i=1;i<=n;i++)
if(viz[i]==0)
dfs(i);
}
void afisare_raspuns()
{
int i,j,l,rasp_size = raspuns.size();
g << rasp_size << endl;
//cout << rasp_size << endl;
for(i=0;i<rasp_size;i++)
{
l = raspuns[i].size();
for(j=0;j<l;j++)
{
g << raspuns[i][j] << " ";
//cout << raspuns[i][j] << " ";
}
g << endl;
//cout << endl;
}
}
int main()
{
citire();
rezolvare();
afisare_raspuns();
}