Pagini recente » Cod sursa (job #572421) | Cod sursa (job #2846783) | Cod sursa (job #159615) | Cod sursa (job #2841129) | Cod sursa (job #2974539)
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
#define NMAX 100005
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m;
int x, y;
vector<int> l[NMAX];
int disc[NMAX], low[NMAX];
bool f[NMAX];
int timp;
stack<int> s;
int counter;
vector<int> ctc[NMAX];
bool stackMember[NMAX];
int i, j;
void dfs(int);
bool comp(vector<int>, vector<int>);
int main()
{
fin >>n>>m;
for (i = 1; i <= m; ++i)
{
fin >>x>>y;
l[x].push_back(y);
}
for (i = 1; i <= n; ++i)
if (!f[i])
{
dfs(i);
}
sort(ctc+1, ctc+counter+1, comp);
fout <<counter<<'\n';
for (i = 1; i <= counter; ++i)
{
for (j = 0; j < ctc[i].size(); ++j)
fout <<ctc[i][j]<<' ';
fout <<'\n';
}
fout.close();
return 0;
}
bool comp(vector<int> a, vector<int> b)
{
return a[0] < b[0];
}
void dfs(int vf)
{
int i; int vfnou;
disc[vf] = ++timp; low[vf] = disc[vf];
f[vf] = 1; s.push(vf);
stackMember[vf] = 1;
for (i = 0; i < l[vf].size(); ++i)
{
vfnou = l[vf][i];
if (!f[vfnou])
{
dfs(vfnou);
low[vf] = min(low[vf], low[vfnou]);
}
else
if (stackMember[vfnou])
low[vf] = min(low[vf], disc[vfnou]);
}
if (disc[vf] == low[vf])
{
counter ++;
while (s.top() != vf)
{
ctc[counter].push_back(s.top());
stackMember[s.top()] = 0;
s.pop();
}
ctc[counter].push_back(s.top());
stackMember[s.top()] = 0;
s.pop();
sort(ctc[counter].begin(), ctc[counter].end());
}
}