Pagini recente » Cod sursa (job #676208) | Cod sursa (job #2588245) | Cod sursa (job #1613591) | Cod sursa (job #2032315) | Cod sursa (job #2972566)
#include <bits/stdc++.h>
#define NMAX 100005
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, numComponents;
vector <int> og[NMAX], tg[NMAX];
stack <int> st;
bool visited[NMAX];
//int component[NMAX];
vector < int > components[NMAX];
void dfs_1(int x)
{
visited[x]=true;
for(int i: og[x])
if(!visited[i]) dfs_1(i);
st.push(x);
}
void dfs_2(int x)
{
//cout<<x<<" ";
//component[x] = numComponents;
components[numComponents].push_back(x);
visited[x]=true;
for(int i: tg[x])
if(!visited[i]) dfs_2(i);
}
void Kosaraju()
{
for(int i=0; i<n; i++)
if(!visited[i]) dfs_1(i);
for(int i=0; i<n; i++)
visited[i]=false;
while (!st.empty())
{
int v=st.top();
st.pop();
if (!visited[v])
{
dfs_2(v);
numComponents++;
//printf("\n");
}
}
}
int main()
{
fin>>n>>m;
int a, b;
while (m--)
{
fin>>a>>b;
og[a].push_back(b);
tg[b].push_back(a);
}
Kosaraju();
fout<<numComponents<<endl;
for(int i=0; i<numComponents; ++i, fout<<endl)
for(int j: components[i])
fout<<j<<" ";
return 0;
}