Pagini recente » Cod sursa (job #1282205) | Cod sursa (job #707965) | Istoria paginii runda/oitse | Cod sursa (job #216965) | Cod sursa (job #2173346)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
#define nmax 100005
ifstream f("ctc.in");
ofstream g("ctc.out");
bool viz[nmax],instk[nmax];
vector<int>Q[nmax];
vector<int>stk,result[nmax];
int n,m,lowest[nmax],niv[nmax],nrcomponente,index;
void read()
{
f>>n>>m;
for (int i=1; i<=m; ++i)
{
int e1,e2;
f>>e1>>e2;
Q[e1].push_back(e2);
}
}
void dfs(int nod)
{
instk[nod]=true;
lowest[nod]=niv[nod]=++index;
stk.push_back(nod);
for (auto w:Q[nod])
{
if (!niv[w])
{
dfs(w);
lowest[nod]=min(lowest[nod],lowest[w]);
}
else if (instk[w])
lowest[nod]=min(lowest[nod],niv[w]);
}
if (lowest[nod]==niv[nod])
{
while (stk.size()&&lowest[stk.back()]>=lowest[nod])
{
result[nrcomponente].push_back(stk.back());
instk[stk.back()]=false;
stk.pop_back();
}
++nrcomponente;
}
}
void solve()
{
for (int i=1; i<=n; ++i)
if (!niv[i])
dfs(i);
g<<nrcomponente<<'\n';
for (int i=0;i<nrcomponente;++i)
{
for (auto w:result[i])
g<<w<<' ';
g<<'\n';
}
}
int main()
{
read();
solve();
return 0;
}