Pagini recente » Cod sursa (job #2768417) | Cod sursa (job #290928) | Cod sursa (job #2635209) | Cod sursa (job #3123482) | Cod sursa (job #2515333)
#include <bits/stdc++.h>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
//-----------------------------------
///Gobale
int n,nr = 1,rasp;
vector<vector<int>>muchii,raspuns;
struct str
{
int index,low;
bool ap;
};
vector<str>v;
stack<int>s;
//-----------------------------------
///Functii
void citire();
void rezolvare();
void afisare();
//-----------------------------------
int main()
{
citire();
rezolvare();
afisare();
return 0;
}
//-----------------------------------
void afisare()
{
g << rasp << '\n';
for(int i = 1; i <= rasp; ++i)
{
for(auto nod : raspuns[i])
g << nod << " ";
g << '\n';
}
}
//-----------------------------------
void calculeaza_ctc(int nod)
{
v[nod].index = nr;
v[nod].low = nr;
nr++;
s.push(nod);
v[nod].ap = 1;
for(auto dest : muchii[nod])
if(v[dest].index == 0)
{
calculeaza_ctc(dest);
v[nod].low = min(v[nod].low,v[dest].low);
}
else if(v[dest].ap)
v[nod].low = min(v[nod].low,v[dest].index);
if(v[nod].low == v[nod].index)
{
rasp++;
raspuns.resize(rasp + 1);
int x;
do
{
x = s.top();
s.pop();
v[x].ap = 0;
raspuns[rasp].push_back(x);
}
while(x != nod);
}
}
//-----------------------------------
void rezolvare()
{
for(int i = 1; i <= n; ++i)
if(v[i].index == 0)
calculeaza_ctc(i);
}
//-----------------------------------
void citire()
{
int m;
f >> n >> m;
muchii.resize(n + 1);
v.resize(n + 1);
while(m--)
{
int a,b;
f >> a >> b;
muchii[a].push_back(b);
}
}