Pagini recente » Cod sursa (job #1814496) | Cod sursa (job #1980813) | Cod sursa (job #2579491) | Cod sursa (job #1734965) | Cod sursa (job #2929835)
#include <iostream>
#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;
void tarjan(int v, vector<vector<int>> adiac, vector<int> &index, vector<int> &lowl, vector<bool> &inStiva)
{
s.push(v);
inStiva[v] = true;
index[v] = k;
lowl[v] = k;
k++;
for(auto vec : adiac[v])
{
if (index[vec] == -1)
tarjan(vec,adiac,index,lowl,inStiva);
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";
cout<<"afis";
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;
vector<int> index(n+1,-1), lowl(n+1,-1);
vector<bool> inStiva(n+1,false);
vector<vector<int>> adiac(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,adiac,index,lowl,inStiva);
}
afis(lowl);
return 0;
}