Pagini recente » Cod sursa (job #1191299) | Cod sursa (job #1711655) | Cod sursa (job #1172939) | Cod sursa (job #2845578) | Cod sursa (job #1358289)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream is("ctc.in");
ofstream os("ctc.out");
int n, m;
vector<vector<int>> g, gt;
vector<vector<int>> sol;
stack<int> stk;
vector<bool> s;
int nrc;
void Df(int x);
void DfTrans(int x, int r);
int main()
{
is >> n >> m;
int x, y;
int r = 0;
sol = vector<vector<int>>(n+1);
g = vector<vector<int>>(n+1);
gt = vector<vector<int>>(n+1);
s = vector<bool>(n+1);
for(int i = 1; i<= m; ++i)
{
is >> x >> y;
g[x].push_back(y);
gt[y].push_back(x);
}
for(int i = 1; i <= n; ++i)
{
if( !s[i] )
Df(i);
}
s.assign(n + 1, false);
while ( !stk.empty() )
{
int i = stk.top();
stk.pop();
if ( !s[i] )
{
r++;
nrc++;
DfTrans(i, r);
}
}
os << nrc << '\n';
for(int i = 1; i <= r; ++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 Df(int x)
{
s[x] = true;
for(const auto & y : g[x])
if(!s[y])
Df(y);
stk.push(x);
}
void DfTrans(int x, int r)
{
s[x] = true;
sol[r].push_back(x);
//os << x << ' ';
for(const auto & y: gt[x])
{
if(!s[y])
DfTrans(y, r);
}
}