Pagini recente » Cod sursa (job #1322819) | Cod sursa (job #236632) | Cod sursa (job #2731073) | Cod sursa (job #877428) | Cod sursa (job #2929842)
#include <fstream>
#include <stack>
#include <vector>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n,m,k,nod;
stack<int> s;
vector<int> index, lowl;
vector<bool> inStiva;
vector<vector<int>> adiac;
vector<vector<int>> ctc;
void tarjan(int v)
{
s.push(v);
inStiva[v] = true;
index[v] = k;
lowl[v] = k;
k++;
for(auto vec : adiac[v])
{
if (index[vec] == -1)
tarjan(vec);
if (inStiva[vec] == true)
lowl[v] = min(lowl[v],lowl[vec]);
}
if(lowl[v] == index[v])
{
vector<int>comp;
do
{
nod = s.top();
lowl[nod] = index[v];
comp.push_back(nod);
inStiva[nod] = false;
s.pop();
}while(nod != v);
ctc.push_back(comp);
}
}
void afis()
{
g<<ctc.size()<<"\n";
int k=0,ok;
for(auto comp: ctc)
{
for(auto v: comp)
g << v <<" ";
g << "\n";
}
}
int main()
{
int a, b;
f >> n >> m;
index.resize(n+1); index.assign(n+1,-1);
lowl.resize(n+1); lowl.assign(n+1,-1);
inStiva.resize(n+1); inStiva.assign(n+1,false);
adiac.resize(n+1);
for (int i = 0; i < m; i++)
{
f >> a >> b;
adiac[a].push_back(b);
}
for (int i = 1; i <= n; i++)
{
if(index[i] == -1)
tarjan(i);
}
afis();
return 0;
}