Pagini recente » Cod sursa (job #2226037) | Cod sursa (job #750312) | Cod sursa (job #1789839) | Cod sursa (job #2676770) | Cod sursa (job #2929841)
#include <fstream>
#include <stack>
#include <vector>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n,m,k,ctc,nod;
stack<int> s;
vector<int> index, lowl;
vector<bool> inStiva;
vector<vector<int>> adiac;
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])
{
do
{
nod = s.top();
lowl[nod] = index[v];
inStiva[nod] = false;
s.pop();
}while(nod!=v);
ctc++;
}
}
void afis(vector<int>lowl)
{
g<<ctc<<"\n";
int k=0,ok;
for (int i = 0; i < n && k != n; i++)
{ok=0;
for (int j = 1; j <= n && k != n; j++)
{
if(lowl[j] == i)
{
g << j << " ";
k++;
ok=1;
}
}
if(ok)
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(lowl);
return 0;
}