Pagini recente » Cod sursa (job #2389613) | Cod sursa (job #1409192) | Cod sursa (job #2380167) | Cod sursa (job #1171272) | Cod sursa (job #1366375)
#include <fstream>
#include <stack>
#include <vector>
using namespace std;
fstream f("ctc.in",ios::in);
fstream g("ctc.out",ios::out);
const int nmax = 100010;
vector <int> a[nmax], tc[nmax];
stack <int> s;
int n, m , i, x, y, nr, nrc, viz[nmax], niv[nmax], low[nmax], inStack[nmax];
void citire()
{
f >> n >> m;
for (i = 1; i <= m; i++)
{
f >> x >> y;
a[x].push_back(y);
}
}
void DFS(int nc)
{
niv[nc] = nr;
low[nc] = nr;
nr++;
viz[nc] = 1;
s.push(nc);
inStack[nc] = 1;
for (vector <int>::iterator it = a[nc].begin(); it != a[nc].end(); ++it)
{
if (viz[*it])
{
if (niv[*it] < low[nc]) low[nc] = niv[*it];
}
else
{
DFS(*it);
if (low[*it] < low[nc]) low[nc] = low[*it];
}
}
if (low[nc] == niv[nc])
{
nrc++;
do
{
x = s.top();
s.pop();
inStack[x] = 0;
tc[nrc].push_back(x);
} while (x != nc);
}
}
int main()
{
citire();
for (i = 1; i <= n ; i++) if (!viz[i]) DFS(i);
g << nrc << '\n';
for (i = 1; i <= nrc; i++)
{
for (vector <int>::iterator it = tc[i].begin(); it != tc[i].end(); ++it) g << *it << " ";
g << '\n';
}
return 0;
}