Pagini recente » Cod sursa (job #692939) | Cod sursa (job #2986507) | Cod sursa (job #1485292) | Cod sursa (job #1224652) | Cod sursa (job #2374320)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ofstream fo("ctc.out");
ifstream fi("ctc.in");
vector<int> vecini[100004];
vector<int> veciniT[100005];
vector<int> CompConex[100005];
stack<int> S;
int n,m,nrComp;
int a,b;
bool viz[100005];
void resetare()
{
for(int i=1; i<=n; i++)viz[i]=false;
}
void DFS(int curent)
{
viz[curent]=true;
for(int v:vecini[curent])
if(viz[v]==false)
DFS(v);
S.push(curent);
}
void DFST(int curent)
{
viz[curent]=true;
CompConex[nrComp].push_back(curent);
for(int v:veciniT[curent])
if(viz[v]==false)
DFST(v);
}
int main()
{
fi>>n>>m;
for(int i=1; i<=m; i++)
{
fi>>a>>b;
vecini[a].push_back(b);
veciniT[b].push_back(a);
}
for(int i=1; i<=n; i++) if(viz[i]==false) DFS(i);
resetare();
while(S.empty()==false)
{
int C=S.top();
S.pop();
if(viz[C]==false)
{
nrComp++;
DFST(C);
}
}
fo<<nrComp<<'\n';
for(int i=1; i<=nrComp; i++)
{
if(CompConex[i].empty()==false)
{
for(auto x:CompConex[i])
fo<<x<<" ";
fo<<'\n';
}
}
fi.close();
fo.close();
return 0;
}