Pagini recente » Cod sursa (job #698376) | Cod sursa (job #1986249) | Cod sursa (job #1935632) | Cod sursa (job #485468) | Cod sursa (job #2075083)
#include <fstream>
#include <vector>
#include <stack>
#define N 100005
using namespace std;
ifstream fin ("ctc.in");
ofstream fout("ctc.out");
int n;
bool viz[N];
vector <int> G[N], GT[N], sol[N];
stack <int> st;
int nrcomp;
void DFS(int x)
{
viz[x] = 1;
for(int i = 0; i < G[x].size(); ++i)
if(!viz[G[x][i]]) DFS(G[x][i]);
st.push(x);
}
void DFST(int x)
{
viz[x] = 0;
sol[nrcomp].push_back(x);
for(int i = 0; i < GT[x].size(); ++i)
if(viz[GT[x][i]]) DFST(GT[x][i]);
}
int main()
{
int m;
fin >> n >> m;
for(int i = 1, x, y; i <= m; ++i)
{
fin >> x >> y;
G[x].push_back(y);
GT[y].push_back(x);
}
fin.close();
for(int i = 1; i <= n; ++i)
if(!viz[i]) DFS(i);
while(!st.empty())
{
int x = st.top();
if(viz[x])
{
DFST(x);
nrcomp++;
}
st.pop();
}
fout << nrcomp << '\n';
for(int i = 0; i < nrcomp; ++i)
{
for(int j = 0; j < sol[i].size(); ++j) fout << sol[i][j] << " ";
fout << '\n';
}
return 0;
}