Pagini recente » Cod sursa (job #3267636) | Cod sursa (job #2686298) | Cod sursa (job #3216795) | Cod sursa (job #2562903) | Cod sursa (job #1461126)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ofstream fout("ctc.out");
ifstream fin("ctc.in");
const int NMAX = 200005;
int n, m, idx, nr;
int lowlink[NMAX], index[NMAX];
bool onStack[NMAX], mark[NMAX];
vector<int> v[NMAX], sol[NMAX];
stack<int> s;
void citire()
{
int x, y;
fin >> n >> m;
for(int i=1; i<=m; i++) {
fin >> x >> y;
v[x].push_back(y);
}
}
void afis()
{
fout << nr << '\n';
for(int i=1; i<=nr; i++) {
for(vector<int>::iterator it=sol[i].begin(); it<sol[i].end(); it++)
fout << *it << ' ';
fout << '\n';
}
}
void strong_connect(int nod)
{
mark[nod] = true;
onStack[nod] = true;
s.push(nod);
idx++;
lowlink[nod] = idx;
index[nod] = idx;
for(int i=0; i<v[nod].size(); i++) {
if(!mark[v[nod][i]]) {
strong_connect(v[nod][i]);
afis(nod);
lowlink[nod] = min(lowlink[nod], lowlink[v[nod][i]]);
afis(nod);
}
else if(onStack[nod]) {
lowlink[nod] = min(lowlink[nod], index[v[nod][i]]);
}
}
if(index[nod] == lowlink[nod]) {
int aux;
nr++;
do{
aux = s.top();
s.pop();
onStack[aux] = false;
sol[nr].push_back(aux);
}while(aux != nod);
}
}
int main()
{
citire();
for(int i=1; i<=n; i++)
if(!mark[i])
strong_connect(i);
afis();
return 0;
}