Pagini recente » Cod sursa (job #599444) | Cod sursa (job #2369795) | Cod sursa (job #623417) | Cod sursa (job #2573641) | Cod sursa (job #1468781)
#include <fstream>
#include <algorithm>
#include <stack>
#include <vector>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector<int> G[100002],co[100001];
int viz[100001], retLv[100002];
bool inStack[100002];
int nrComp, check,n,m, nod1, nod2, level;
stack<int> stiva;
void DFS(int nod)
{
int mylevel = ++level;
viz[nod] = check; retLv[nod] = level;
stiva.push(nod); inStack[nod] = 1;
for(int i=0;i<G[nod].size();i++)
if(viz[G[nod][i]] == 0)
{
DFS(G[nod][i]);
if(retLv[G[nod][i]] < retLv[nod])
retLv[nod] = retLv[G[nod][i]];
}
else
if(viz[G[nod][i]] == check && inStack[G[nod][i]])
{
if(retLv[G[nod][i]] < retLv[nod])
retLv[nod] = retLv[G[nod][i]];
}
if(retLv[nod] == mylevel)
{
nrComp ++;
while(stiva.top() != nod)
{
co[nrComp].push_back(stiva.top());
inStack[stiva.top()] = 0;
stiva.pop();
}
co[nrComp].push_back(nod);
inStack[nod] = 0;
stiva.pop();
}
}
int main()
{
fin>>n>>m;
for(int i=1;i<=m;i++)
{
fin>>nod1>>nod2;
G[nod1].push_back(nod2);
}
for(int i=1;i<=n;i++)
if(viz[i]==0)
{
check++;
level = 0;
DFS(i);
}
fout<<nrComp<<'\n';
for(int i=1;i<=nrComp;i++)
{
sort(co[i].begin(),co[i].end());
for(int j=0;j<co[i].size();j++)
fout<<co[i][j]<<' ';
fout<<'\n';
}
return 0;
}