Pagini recente » Cod sursa (job #373156) | Cod sursa (job #1846182) | Cod sursa (job #539499) | Cod sursa (job #1055187) | Cod sursa (job #943114)
Cod sursa(job #943114)
#include <fstream>
#include <vector>
#include <stack>
#define Nmax 100005
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m;
int viz[Nmax], k;
vector <int> vecin1[Nmax], vecin2[Nmax], sol[Nmax];
stack <int> s;
void citire()
{
int i, x, y;
fin >> n >> m;
for(i = 1; i <= m; ++i)
{
fin >> x >> y;
vecin1[x].push_back(y);
vecin2[y].push_back(x);
}
}
void df1(int nod)
{
vector <int> ::iterator it;
viz[nod] = 1;
for(it = vecin1[nod].begin(); it != vecin1[nod].end(); ++it)
if(viz[*it] == 0)
df1(*it);
s.push(nod);
}
void df2(int nod)
{
vector <int> ::iterator it;
viz[nod] = 0;
sol[k].push_back(nod);
for(it = vecin2[nod].begin(); it != vecin2[nod].end(); ++it)
if(viz[*it] == 1)
df2(*it);
}
void kosaraju()
{
int i;
for(i = 1; i <= n; ++i)
if(viz[i] == 0)
df1(i);
while(!s.empty())
{
if(viz[s.top()] == 1)
{
++k;
df2(s.top());
}
s.pop();
}
}
void afisare()
{
vector <int> ::iterator it;
fout << k << '\n';
for(int i = 1; i <= k; ++i)
{
for(it = sol[i].begin(); it != sol[i].end(); ++it)
fout << *it << " ";
fout << '\n';
}
}
int main()
{
citire();
kosaraju();
afisare();
return 0;
}