Pagini recente » Cod sursa (job #90737) | Cod sursa (job #1054375) | Cod sursa (job #1527930) | Cod sursa (job #2119317) | Cod sursa (job #2928630)
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
ifstream f("ctc.in");
int n,m;
vector<vector<int>> la;
vector<vector<int>> raspuns;
stack<int> stiva;
int low[100001],viz[100001],ctc[100001];
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] = curent;
ctc[curent] = 1;
viz[curent] = 1;
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(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();
cout << rasp_size << endl;
for(i=0;i<l;i++)
{
l = raspuns[i].size();
for(j=0;j<l;j++)
cout << raspuns[i][j] << " ";
cout << endl;
}
}
int main()
{
citire();
rezolvare();
afisare_raspuns();
}