Pagini recente » Cod sursa (job #1639178) | Cod sursa (job #3190695) | Cod sursa (job #2428746) | Cod sursa (job #277841) | Cod sursa (job #1255019)
#include <fstream>
#include <stack>
#include <vector>
using namespace std;
ifstream is("ctc.in");
ofstream os("ctc.out");
vector<vector<int>>g;
vector<vector<int>>gt;
stack<int> stk;
vector<bool> s;
vector<vector<int>> sol;
int n, m, nrsol, r;
void Read();
void Dfs1(int x);
void Dfs2(int x, int r);
int main()
{
Read();
for(int i = 1; i <= n; ++i)
{
if(!s[i])
Dfs1(i);
}
s.assign(n+1, false);
int k;
while(!stk.empty())
{
k = stk.top();
stk.pop();
if(!s[k])
{
nrsol++;
Dfs2(k, nrsol);
}
}
os << nrsol << '\n';
for(int i = 1; i <= nrsol; ++i)
{
for( vector<int>::iterator it = sol[i].begin(); it != sol[i].end(); ++it)
os << *it << ' ';
os << '\n';
}
is.close();
os.close();
return 0;
}
void Read()
{
is >> n >> m;
g = vector<vector<int>>(n+1);
gt = vector<vector<int>>(n+1);
sol = vector<vector<int>>(n+1);
s = vector<bool>(n+1);
int x, y;
for(int i = 1; i <= m; ++i)
{
is >> x >> y;
g[x].push_back(y);
gt[y].push_back(x);
}
}
void Dfs1(int x)
{
s[x] = true;
for(vector<int>::iterator it = g[x].begin(); it != g[x].end(); ++it)
if(!s[*it])
Dfs1(*it);
stk.push(x);
}
void Dfs2(int x, int r)
{
s[x] = true;
sol[r].push_back(x);
for(const auto& y : gt[x])
if(!s[y])
Dfs2(y, r);
}